KMP算法 详解+模板
KMP算法详解。字符串匹配走一波！
本文大部分摘自szy学长的ppt《string》中的KMP部分。
%%%膜拜szy大神orz
1.概述
KMP 算法是用来解决单模匹配问题的一种算法。
如果暴力的进行单模匹配，那么时间复杂度为O(nm)。
KMP 算法通过对模式串的预处理优化了复杂度。
2.求next数组
为了叙述方便，设模式串长度为n，主串长度为m。
将模式串称为s1，主串称为s2，下标从1 开始。
我们首先对模式串预处理出一个next 数组。
next[i] 表示最大的x，满足s1[1 : x – 1] 是s1[1 : i – 1] 的后缀。
这个数组记录了失配时，模式串指针移动的目标位置。
求next[i] 时，考虑维护一个位置j，初始时为next[i – 1]。
如果s1[j] = s1[i -1]，那么next[i] 显然等于j + 1。
如果s1[j] != s1[i – 1]，那么此时需要将j 向前移动到next[j] 的位置。
一直将j 移动到next[j] 的位置，直到j = 0 或s1[j] = s1[i – 1]。
此时next[i] 等于j + 1。
由于next 是最长公共前后缀，因此在j 的移动过程中一定会经过next[i] – 1 的位置。
1 void getnx() 2 { 3 nx[1]=0; 4 for(int i=2,j=1;i<=n;) 5 { 6 nx[i]=j; 7 while(j&&s1[j]!=s1[i])j=nx[j]; 8 j++,i++; 9 } 10 }
3.匹配
在匹配过程中，设在主串中匹配到位置i，模式串中匹配到位置j。
首先如果s2[i] = s1[j]，当前位置匹配成功，此时可以把i 和j 同时移动到下一个位置。
否则发生失配，需要进行调整，我们将j 置为next[j]，然后继续匹配。
同样由于next 是最长公共前后缀，因此在j 的移动过程中不会跳过可能匹配的位置。
并且模式串中j 之前的部分一定可以匹配。
void kmp() { for(int i=1,j=1;i<=m;) { while(j&&s1[j]!=s2[i])j=nx[j]; if(j==n) { // 此时找到了一个能够匹配的位置 j=nx[j]; } else j++,i++; } }
可以发现两部分代码有很大相似之处。
其实可以把求next 数组过程看做用模式串与自身匹配的过程。
4.时间复杂度
在求next 的过程中，j 指针每向后移动一步，i 指针就会向后移动一步。
而j 指针每延next 移动一次，就会向前移动大于等于一步。
由于i 指针会向后移动O(n) 次，因此j 指针也只会向后移动O(n) 次，因此向前同样最多移动O(n) 次。
因此求next 数组部分复杂度为O(n)。
与之类似，可以得出匹配过程的复杂度为O(m)。
因此KMP 算法的总复杂度为O(n + m)。
尾声：
总之，KMP算法是处理字符串匹配问题的一大利器。
搭配字符串上的DP可以说是……咳咳……很有趣……
（下篇高能预告）