匹配_KMP模式匹配算法：二

预处理操作

参数

• iterP_begin:模式序列P的起始迭代器
• iterP_end:模式序列P的终止迭代器

解析

初始化
pai[1] = 0,k = 0

遍历(q从：2->m)
从2开始，因为Pk必须是Pm的真子集。
条件：k > 0 && p[k+1] != p[q]
终止条件：k = pai[k],因为p[k+1]=p[q]说明找到了pk是pm的真子集
p[k+1] == p[q],则,k = k+1 && pai[q] = k

KMP字符串匹配算法

参数

• iterT_begin : 被文本序列T的起始迭代器
• iterT_end: 文本序列T的终止迭代器
• iterP_begin : 模式序列P的起始迭代器
• iterP_end: 模式序列P的终止迭代器

字符串匹配

定义如下：假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，
其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。
字符数组P和T通常称为字符串。

原理

模式的前缀函数pai 包含了模式与它自身偏移进行匹配的信息。假设模式字符P[1...q]与文本字符T[s+1,...s+q]匹配，s'是某个偏移量，s'>s。则对于某些k<q，满足：P[1...k]=T[s'+1,...s'+k]的最小s'>s，其中s'+k=s+q?

换句话说，已知Pq是T[s+q]的后缀，我们希望Pq的真前缀 Pk 也是T[s+q]的后缀。我们把在P前缀长度
范围内的差值 q-k 加到s上即可得到新的偏移 s'=s+(q-k)。

可以用模式与它自身的比较来预先计算出这些必要的信息。前述可知Pk是T[s+q]的后缀，它也是Pq的真前缀，因此要求出 Pk是Pq的后缀的最大的k<q。于是这个新的偏移s'=s+(q-k)就是下一个可能的有效偏移。
之所有求最大的k，就是为了是(q-k)尽可能小，从而不会漏过任何的可能的有效偏移。

模式P的前缀函数就是函数 pai:{1,2,...,m}--> {0,1,2,...,m-1}，满足：
pai[q]=max{k:k<q 且 Pk是Pq的后缀}。即pai[q]是Pq的真后缀P的最长前缀长度。

辅助函数

KMP 算法用到了辅助函数 pai，它在O(m)时间内根据模式预先计算出pai并且存放在数组pai[1...m]中。
数组pai能够使我们按照需要即时计算出转移函数。
计算出pai数组之后，KMP算法从左到右扫描文本序列T，并从pai中获取转移函数。当状态结果为 m时，当前偏移为有效偏移点。

步骤

• 预处理算法
• 匹配算法

初始化
q = 0

遍历(i从：1->n)
条件：q > 0 && p[q+1] != T[i];在循环中执行q=pai[q]
如果：P[q+1]==T[i]则q=q+1
如果：q==m,则找到了有效偏移点。将结果保存，然后q=pai[q]

性能

计算前缀函数的运行时间为 O(m)，匹配时间为O(n)，总运行时间为 O(n).