分类标签归档:字符匹配

多模式匹配算法AC

1 AC 算法概况

AC 算法,即 Aho-Corasick 自动机算法,是两位创始人的名称凑出来的(国际惯例起名法了属于是,但是简称和强化学习里的 Actor-Critic 算法重名,需要注意区分~)

此算法的时间复杂度为O(n),与匹配字符串的数目无关,只跟被匹配字符串长度有关

特性:核心思想和单模式匹配算法KMP(建议先看懂这个)是一致的,都通过寻找字符串的内部规律,达到每次失配时的高效跳转,只不过AC算使用前缀树来存放所有模式串的前缀,然后通过失配指针来处理失配的情况。

Read more

单模式匹配算法KMP

1 KMP 算法概况

KMP,全称为Knuth-Morria-Pratt,是三位创始人的名称凑出来的

KMP 算法是一种字符串匹配算法,时间复杂度 :O(n+m)

特性:字符串头部和尾部会有重复的部分,利用这部分信息,减少匹配次数

理解字符串的前缀和后缀

  • 把字符串切割成非空的两份,前面那份就是前缀,后面那份就是后缀
  • 所有前缀的可能性组成了前缀集合,所有后缀的可能性组成了后缀集合,比如”Harry”的前缀集合是{”H”, ”Ha”, ”Har”, ”Harr”},而”Potter”的后缀集合是{”otter”,

Read more