KMP

In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. 字符串搜索/匹配算法在大规模文本应用中有非常重要的作用，比如文章敏感词搜索，多关键词过滤搜索等。如果使用暴力搜索，则时间复杂度很高（若 m 为关键字的长度， n 为要待搜索的字符串长度， k为关键字数量，则复杂度为$O(n \times m \times k)$。而好的算法可以让这些问题的时间复杂度大大降低。 常用的算法有Knuth–Morris–Pratt(KMP), Boyer-Moore(BM), Rabin-Karp(RK), Trie, Trie图, AC自动机等. 一个实例 匹配时，想象我们拿着模式字符串pat=ABABAC, 像尺子一样从左到右对齐依次匹配如图的txt。 从txt[i=0]开始, 把pat的开头pat[j=0]对齐txt[0], 开始比较pat[0]和txt[0], 发现不匹配, 暴力的算法是从txt下一个字符重新开始i=1, 同时把尺子也右移一位对齐新的txt起始点. 从i=3开始, 发现一开始可以匹配上(pat[j=0] == txt[3]), 那么保持尺子不动, 开始比较pat[j+1]和txt[i+1], 结果不匹配. 从i=4开始, 情况也类似, 而且发现连续匹配上了pat[++j]和txt[++i], 假如运气好, 我们能匹配完整个尺子, 那么达到目的. 可惜在i=7时失败了. 问题的关键就是i=3和i=7这里, 特别是i=7, 假如还是用暴力解法1操作, 那么需要重新比对txt[i=5,6,7...]. 但前面已经匹配了一半的尺子了, 那么其实我们已经知道了txt的后缀txt[4,5,6]和尺子的前缀pat[0,1,2]重合, 我们能否利用这个信息来优化算法? 按照前面的分析, 每一个已匹配的前缀等于txt中已匹配的后缀, 那么txt后缀后面可能接的字符有R种, 我们可以提前计算每一个已匹配txt后缀后接每一种字符时, 应该怎么做. ...