pat[0...M]为模式串,长度为$M$ txt[0...N]为文本串,长度为$N$ 我们需要从$txt$中寻找$pat$串的位置

kmp基本思想 利用最长公共前后缀确定匹配失败后的位置达到快速匹配的效果 算法分两部分:

• 预处理$pat$串
• $txt$串搜索$pat$串

Preprocessing algorithm

预处理求出模式串$pat$的最长公共前后缀数组: lps[]

Name lps indicates longest proper frefix which is also suffix. A proper prefix is prefix with whol string not allowed.

lps[i] = the longest proper prefix of pat[0..i] which is also a suffix of pat[0..i]. Examples of lps[] construction:

For the pattern “AAAA”, lps[] is [0, 1, 2, 3]

For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]

For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]

这里要注意的是: 前缀是包含第一个字符且不包含最后一个字符的子串. 后缀是包含最后字符且不包含第一个字符的子串. 进一步说明lps的含义, 设lps[i-1] = k; 则表明在pat[0...i-1]存在pat[0,k-1]=pat[i-k+1...i], 即pat开头的k个字符组成的字符串a与pat结尾的k个字符串相同b.

接下来说如何求得lps 这里利用的是动态规划的思想, 逐个求出lps[0]到lps[i]. 显然当i=0时 lps[0]=0 当i>0时, 求lps[i], 可利用已求出的lps[0...i-1] 设lps[i-1]=k1, 则可知pat串在i位置前k1个字符与前k1个字符分别组成的字符串相等, 即pat[0...k1-1]=pat[i-k1, k1-1] 要得出lps[i-1]只需要比较pat[k1]是否等于pat[i]即可

• 相等, 则lps[i]=k1+1
• 不等, 则令k1=lps[k1-1], 继续以上过程

例如当lps[k1-1]=k2 时：

由于黄色区域都是相等的, 所以pat[0...k2]=pat[i-k2...i-1], 仅需比较pat[k2]与pat[i]是否相同, 若相同则lps[i] = k2+1;

computeLPSArray1 实现了上述过程，注意到第i次外层循环len的变化由lps[i-1]变为lps[i]-1 ,内层循环的次数不超过lps[i-1]-lps[i]+1 ，总内循环次数$\sum \limits_{i=1}^{n-1}lps[i-1] + lps[i]+1 = n-lps[n]$，所以总时间复杂度$O(n)$ computeLPSArra2 则是整合了两个循环为一个，与第一种实现无本质区别。

Searching Algorithm

搜索算法就比较简单. 比较pat[j] 与 txt当前窗口中的字符.