Multiple String Searching

26th November 2019 at 10:52am
Algorithm: String

Aho–Corasick

掌握程度使用,不理解算法
时间复杂度O(m+n),m 为被搜索串长度,n 为要匹配的模式个数
空间复杂度未知
各语言实现C, C, Java, JavaScript, Python

Aho-Corasick 算法主要用于这样的场景:给定多个字符串模式和一串待搜索的字符串,要求把各个字符串模式在被搜索的字符串中出现的位置计算出来。比如有以下输入参数:

  • 被搜索的字符串:Across the Great Wall, we can reach every corner in the world
  • 欲匹配的字符串模式:he, all, an

则这个算法会在线性时间内,把 he 的位置(9),all 的位置(19)以及 an 的位置(28)搜索出来。

FlashText

FlashText 是一个快速查找和替换字符串的算法及 Python 实现。