王半仙的学习分享

1 AC 算法概况

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

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

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

Read more

1 KMP 算法概况

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

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

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

理解字符串的前缀和后缀

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

Read more