野生皮皮虾攻击力多大:【串和序列处理 5】KMP子串匹配算法

模式匹配：在字符串S中，子串P的定位操作通常称做串的模式匹配。说白了，就是在一个字符串中寻找子串。在Suffix Trie和PAT tree中我们已经讨论过匹配子串的方法了。这里我们讨论一种线性匹配算法来寻找子串。

例： 我们要在S="ababcabcacbab"中查找子串P="abcac"。下图左侧是一种很普通的模式匹配算法

  
这种普通的模式匹配算法很简单，但时间复杂度是O(n*m)。其中n=S.length，m=T.length. 代价很高。难道真的要像第三趟到第四趟那样：好不容易匹配到S中的第7个位置，但由于不相同，则有回溯到第4个位置重新开始。

其实，每一次匹配过后，主串S中被匹配过的位置其实不用再匹配了。也就是上一趟匹配结果对下一趟有指导作用。我们用一个证明来说明这一点(假如主串S=s1 s2 .... sn ，模式串P=p1 p2 ... pm )。

证明：当一趟匹配完成之后，我们发现si !=pj 。那么至少说明了模式串p1... p(j-1)是匹配成功的。也就是得到了： p1 p2 ... p(j-1) = s(i-j+1) s(i-j+2) ..... s(i-1) 。比如第三趟 s7!=p5 => s2...s6=p1...p4 = "abca".

如果像上图左侧算法那样，从第三趟i=7回溯到第四趟i=4是有必要的话，那么也说第四趟可能完全匹配到了模式串P。好，我们现在就假设si != sj之后，i 回溯主串(i-j+1)的下一个位置上可以匹配成功模式串P，那么我们可以得到 p1 p2 ... p(j-1) =s(i-j+2) s(i-j+3) ... s(i)。

合并下标蓝色的两个式子，我们可以得到：

s(i-j+1) s(i-j+2) ..... s(i-1)=s(i-j+2) s(i-j+3) ... s(i)

也就是： s(i-j+1)=s(i-j+2)=s(i-j+3)= .... =s(i-1)=s(i)

我靠，主串S中全部的字符都一样，这种情况下才必须每一次都回到主串的下一个位置上重新开始。而只要有字符不同，就完全没有这个必要了。好了，基于这个证明成果，我们开始介绍KMP算法。

KMP 模式匹配—— D.E.Knuth V.R.Pratt和J.H.Morris同时发现的。因此人们称它为克努特-莫里斯-莫拉特操作（简称KMP算法）。KMP的优势在于当每一趟匹配结果中出现了不等情况时，主串并不需要回溯位置i (上面已经证明)，而只要回溯模式串P即可。也就是说，只需要在主串S的位置i 处重新与模式串的位置k进行比较(如上图右侧过程)。 那么这个重新需要定位的模式串k位置有什么要求呢，或者说我们怎么确定这个k呢。我们再用一个小小的证明来揭示(还是假如主串S=s1 s2 .... sn ，模式串P=p1 p2 ... pm )：

证明：当一趟匹配完成之后，我们发现si !=pj 。此时首先可以肯定的是k< j，因为模式串j 必须回溯。

如果 s1 与 pk 有重新比较的必要，那么模式串P前k-1个字符必须满足下列关系式：

p1 p2 ... p(k-1)=s(i-k+1) s(i-k+2) ... s(i-1)

此外，由于经过额一趟的匹配之后，已经可以得到“部分匹配”结果，主串S中i 位置的前k个字符一定等于模式串P中j 位置上的前k个字符：

p(j-k+1) p(j-k+2) ... p(j-1) = s(i-k+1) s(i-k+2) ..... s(i-1) 。

合并两个蓝色的式子：

p1 p2 ... p(k-1) = p(j-k+1) p(j-k+2) ... p(j-1)

我们发现了，位置k的值取决于模式串P自己必须满足上面这个红色的式子。

失效函数：当在模式串P的第j 个位置上发生匹配不成功时，需要将模式串回溯到位置 k处的这样一个f(j)=k的函数，就叫做失效函数。其中j 和k 的值必须满足p1 p2 ... p(k-1) = p(j-k+1) p(j-k+2) ... p(j-1)。也就是说pj 的前k-1个字符必须等于pk 的前k-1 个字符。因此，失效函数f(j)的定义如下：

0 当j=1时

f(j) = Max{k|1

1 不满足上面的情况

比如模式串P=“abcac”的每一个位置的失效函数如下：

j 1 2 3 4 5

P a b c a c

k=f(j) 0 1 1 1 2

失效函数的算法

假如f(j)=k，则表明 p1...p(k-1) = p(j-k+1)...p(j-1)。这说明pj 的前k-1个字符必须等于pk 的前k-1 个字符。也就是说p1...pk一定是p1...pj的一个后缀子串。因此我们可以把模式串P与自身做KMP算法的匹配来求解这个K值。算法如下：

(1) 若 pk=pj, 则p1...p(k-1)pk=p(j-k+1)...p(j-1) pj 。 表明f(j+1)=k+1

(2) 若 pk!=pj , 则可以把求f(j+1)看成以P为主串和匹配串的模式匹配问题。即 pk!=pj 则比较pj与p(f(k))，如果pj==p(f(k))，则f(j+1)=f(k)+1。否则继续比较下去直到f(k)=0为止。

失效函数算法的运行时间是o(m).

KMP算法Java源代码

1. package net.hr.algorithm.string;
3. public class KMP {
5. private int[] next=null;
6. private char[] mainAry=null;
7. private char[] patternAry=null;
9. public KMP(String main,String pattern){
11. this.mainAry=new char[main.length()+1];
12. this.patternAry=new char[pattern.length()+1];
13. System.arraycopy(main.toCharArray(),0,mainAry,1,main.length());
14. System.arraycopy(pattern.toCharArray(),0,patternAry,1,pattern.length());
15. this.next=new int[pattern.length()+1];
16. }
17. /**
18. * KMP匹配
19. * @param pos 从主串起始位置开始
20. */
21. public int match(int pos){
23. if(pos>mainAry.length)
24. throw new IndexOutOfBoundsException();
25. failFunction();
27. int i=pos,j=1;
28. while(i
29. if(j==0||mainAry[i]==patternAry[j]){
30. ++i;
31. ++j;
32. }else{
33. j=next[j];
34. }
35. }
36. if(j>=patternAry.length) return i-patternAry.length+1;
37. else return 0;
38. }
39. /**
40. * 匹配串失效函数
41. */
42. private void failFunction(){
44. int i=1,j=0;
45. next[1]=0;
46. while(i
47. if(j==0||patternAry[i]==patternAry[j]){
48. next[++i]=++j;
49. }else{
50. j=next[j];
51. }
52. }
53. }
55. /**
56. * 测试
57. * @param args
58. */
59. public static void main(String[] args) {
61. KMP kmp=new KMP("acabaabaabcacaabc","abaabcac");
62. System.out.println(kmp.match(1));
63. }
65. }

package net.hr.algorithm.string;public class KMP {private int[] next=null;private char[] mainAry=null;private char[] patternAry=null;public KMP(String main,String pattern){this.mainAry=new char[main.length()+1];this.patternAry=new char[pattern.length()+1];System.arraycopy(main.toCharArray(),0,mainAry,1,main.length());System.arraycopy(pattern.toCharArray(),0,patternAry,1,pattern.length());this.next=new int[pattern.length()+1];}/** * KMP匹配 * @param pos 从主串起始位置开始 */public int match(int pos){if(pos>mainAry.length)throw new IndexOutOfBoundsException();failFunction();int i=pos,j=1;while(i=patternAry.length) return i-patternAry.length+1;else return 0;}/** * 匹配串失效函数 */private void failFunction(){int i=1,j=0;next[1]=0;while(i
KMP算法效率
对于长度为n的文本串和长度为m的模式串进行模式匹配的运行时间为O(n+m). 很显然，因为文本串在KMP算法中并不需要回溯，因此与模式串的比较次数为O(n)。但模式串要建立失效函数，所付出的代价是O(m)。因此总体的时间复杂度是O(m+n)。实际中，m要远小于n，因此近似可以认为KMP效率为O(n)。
但是KMP算法有种最坏的情况，当模式串P="aaaaa"时，即每一个字符都一样的时候。则失效函数为：
j 1 2 3 4 5 
P a a a a a
f(j) 0 1 2 3 4
此时如果主串中的s[i]!=p[j]的时候，根据模式串P回溯j=f(j)的原则。s[i]需要从模式串P的最后一个字符一步一步回溯到第一个字符，每次都要比较一遍。这时的时间复杂度为O(m)。那么对于n个字符的S串而言，最差的时间复杂度就是O(n*m)了，退化成了蛮力匹配。
KMP和后缀树都可以用来匹配子串。因此我们这里与后缀树做一个比较，虽然后缀树在查找的过程中只需要大概O(m)的时间复杂度。对长度n的文本串建立后缀树最好的算法需要O(n)时间复杂度，因此后缀树大致也需要O(n+m)。