数据结构-KMP算法

1、kmp算法 它是：在一个长字符串中匹配一个 短子串的无回溯算法。 定义 s: 模式串 , m: 模式串的长度 text: 要匹配的字符串, n:text的长度 设text: x1,x2,xn , s: a1,a2,am, 则当存在i 使 xi+k=ak(k=1,2,m)时，认为text与模式串 匹配，当然text也可能与模式串有多处匹配 例如：text: abcabca, s:abc 则text与s匹配的 位置有3和6 朴素算法 枚举text中的每一个位置，判断以该位置为 起始位置的长度为m的子串是否与s匹配. 显然时间复杂度为o(m*n) 伪代码如下 void fun(char *text,

2、char *s) for(i=0;texti;i+) for(j=0;jm;j+) if(texti + j!=sj) break; if(j=m) printf(“匹配成功n”); return ; printf(“无法匹配n”); kmp算法 作为一种无回溯的算法，它是高效的，待 会儿你将看到它的时间复杂度为o(m+n)， 空间复杂度也为o(m+n) 而且，它很容易理解，代码也很短 定义 next: 为对应模式串的数组 设字符串为 s1s2s3.sm ,其中s1，s2，s3，. si，. sm均是字符，则nexti=m，当且仅当 满足如下条件：字符串s1s2.sm equals 字符 串s

3、(i-m+1).si-1 si 并且s1s2.sm s(m+1) unequals s(i-m) s(i-m+1).si-1 si。 通俗地讲，nexti保存了以si为结尾的后缀 与模式串前缀的最长匹配数。 定义 例如： s:a b c a b c d d e a next:0 0 0 1 2 3 0 0 0 1 i=5时，后缀有c,bc,abc,cabc,bcabc,abcabc; 相应的前缀为:a,ab,abc,abca,abcab,abcabc s: a b a b a c b next: 0 0 1 2 3 0 0 kmp算法的运行过程 我们用两个指针i和j分别表示，ai-j+ 1.i

4、与 b1.j完全相等。也就是说，i是不断增加的， 随着i的增加j相应地变化，且j满足以ai结 尾的长度为j的字符串正好匹配b串的前 j个 字符（j当然越大越好），现在需要检验 ai+1和bj+1的关系。 如果ai+1=bj+1,i和j各加1，什么时候 j=m，就说b是a的子串（b串已经整完了） kmp算法的运行过程 如果ai+1!=bj+1,这时候怎么办？ i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 j=5时，ai+1!=bj+1,我们要把j改成比它小 的值j。改成多少合

5、适呢？ kmp算法的运行过程 i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 记住，我们要保持ai-j+ 1.i与b1.j完全相 等，因而j是最大的数使ai-j+1.i与b1.j 完全相等. kmp算法的运行过程 i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 显然是求一个最长的以i为末尾的后缀要与b 的前缀匹配。由于ai-j+ 1.i与b1.j完全相 等,

6、故令j=nextj即可保证此性质保留 kmp算法的运行过程 i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 kmp算法的运行过程 需要注意的是i并没有动，改变的只是j的值 如果改变j的值后ai+1仍不等于bj+1的话， 继续改变j值直到ai+1=bj+1或者j=0 j=0表示i+1前面无论怎么匹配都不能使 ai

7、+1=bj+1,只好让ai+1与bj+1单独匹配 还是上一个例子，再演示一下 kmp算法的运行过程 i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 当i=6,j=5时，ai+1!=bj+1,故令j=next5=3 kmp算法的运行过程 i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 此时i=6,j=3 仍不满足ai+1=bj+1，故继续 减小j,使j=nex

8、t3=1 kmp算法的运行过程 i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 此时i=6,j=1 仍不满足ai+1=bj+1，故继续 减小j,使j=next1=0 kmp算法的运行过程 i = 1 2 3 4 5 6 7 8 9 a = a b a b a b a a b a b b = a b a b a c b j = 1 2 3 4 5 6 7 终于，a8=b1，i变为8，j为1 kmp算法的运行过程 i = 1 2 3 4 5 6 7 8 9 a = a b a b

9、 a b a d b a b b = a b a b a c b j = 1 2 3 4 5 6 7 事实上，有可能j到了0仍然不能满足 ai+1=bj+1（比如a8=“d”时）。因此，准 确的说法是，当j=0了时，我们直接增加i值 但忽略j直到出现ai=b1为止。 kmp代码 /kmp j = 0; for(i = 0; i 0 if(ai = bj) j+; else j = 0; next数组 /next memset(next, 0, sizeof(next); for(i = 1; i bn; i+) temp = nexti - 1; while(temp if(btemp = b

10、i) nexti = temp + 1; else nexti = 0; 时间复杂度分析 由于while循环的不确定性，好像时间复杂 度很高. 但事实上，我们可以看到无论是j还是temp， 它只在程序的最后+1，故最多+n(+m)。因而 while循环最多-n(-m),因而算法的复杂度都 是线性的. next的复杂度o(m),kmp的复杂度为o(n) 关于next的一个性质 问题的提出: 关于next的一个性质 现在的问题是：如何快速找出s的最小循环 周期（循环节）呢？ len是s的长度 给出结论：如果len%(len-nextlen-1)=0,则 字符串中必存在最小循环节，且循环次数 即为

11、len/(len-nextlen-1) 关于next的一个性质 证明：必要性：因为字符串中存在最小循环节 (设长度为k)，nextlen-1=len-k,所以len%(len- nextlen-1)=0; 充分性：令k1=len-nextlen-1,由于k1整除len, 所以可以相应的把len划分为n片区域 (n=len/(k1)，从小到大依次表示为 t1,t2.tn;由next数组的定义可知， t1=t2,t2=t3,.t(n-1)=tn,且相应的片区域即为最 小，所以循环次数也为len/(len-nextlen-1); 关于next的一个性质 例：poj 2406 题意：给你一串字符串，问

12、它的循环次数 sample input: abcd aaaa ababab sample output 1 4 3 核心代码如下 if(n%(n-nextn-1)=0) printf(%dn,n/(n-nextn-1); else printf(1n); 关于next的一个性质 补充一下： s: abcabcabca n-nextn-1=3,虽然10%3！=0，但是它有理论意义， 可以看到若在s后面加上bc，abc就又是最小循环周 期了。 故这里要注意的是len - nextlen - 1为这个串的最小 循环节的长度，这不需要最后的子串是完整 的； if(len % (len nextlen

13、- 1) = 0)这个求得的是 串的最大的循环的个数这个要求最后的子串是完整 的 思考 kmp不仅仅是匹配完全相等的情况，其思想 完全适用于对一定规律的字符进行匹配 eg: /problem?id=3167 关于扩展kmp（了解） 我们先比较一下kmp和扩展kmp所表示的意义 kmp： next数组的性质是模式串中每一个位置的前缀和此串其实后 缀的最大匹配个数 kmp匹配时的性质是求出模板串在主串中出现的位置 扩展kmp： next数组的性质是模板串中每一个位置的后缀和此串前缀匹 配的最大个数 kmp匹配的性质是主串中的每个位置和模板串的最多匹配个 数。 可以看到km

14、p匹配的是模式串的长度，显然扩展kmp是kmp 的一种扩展 扩展kmp 像求kmp的next数组一样，我们先求ai，表示模式 串的后缀和模式串的最长公共前缀,然后再利用ai求 出bi 说明一下a的求法，b同理 现在我们要求ai，且a1-ai-1已经求出，设k，且 1=k=i-1，并满足k+ak最大 所以tk-tk+ak-1=t0-tak-1，推出ti- tk+ak-1=ti-k-tak-1 令l=ai-k，若l+i-1k+ak-1，由a是最长公共前缀知 ai=l，否则，向后匹配，直到字符串失配 并相应更新 扩展kmp 关于复杂度： 很容易看出，在计算的过程中，凡是访问 过的点，都不需要重新访问

15、了。一旦比较 ，都是比较以前从不曾探访过的点开始。 因此总的时间复杂度是o(n+m),是线性的。 扩展kmp /求模板串中的a数组 j = 0; while(t0+j=t1+j) j = j + 1; int a1 = j,k = 1; for(int i=2;im;i+) int len = k + ak 1,l = ai-k; if( l len - i + 1 ) ai = l; else j = max(0,len -i +1); while(ti+j = t0+j) j = j + 1; ai = j，k = i; 扩展kmp /求主串中的b数组 j = 0; while(t0+j=s0+j) j = j + 1; int b0 = j,k = 0; for(int i=1;im;i+) int len = k + bk - 1,l