KMP算法

发表于   |  

KMP算法笔记。

详见KMP算法wiki

KMP算法对蛮力的改进主要在当失配的时候，模式串不是移动一位，而是根据模式串本身的特性进行移动多位，来提升匹配的速度。

这里关键一步就是求出失配时该移动多少位，也就是常说的next数组。

这篇文章对next数组的讲解比较简单易懂。

next数组就是模式串的最长的相等的前缀和后缀的长度。比如ababacb

  • next[0]: a的前缀和后缀是都是空，则next[0]=0
  • next[1]: ab的前缀是[a]，后缀是[b]，没有相等的前缀和后缀，所有next[1]=0
  • next[2]: aba的前缀[a，ab]，后缀是[a，ba]，最长的相等的前缀和后缀是a，所有next[2]=1
  • next[3]: abab的前缀[a，ab，aba]，后缀是[a，ab，bab]，最长的相等的前缀和后缀是ab，所有next[3]=2
  • next[4]: ababa的前缀[a，ab，aba，abab]，后缀是[a，ba，aba，baba]，最长的相等的前缀和后缀是aba，所有next[4]=3
  • next[5]: ababac的前缀[a，ab，aba，abab，ababa]，后缀是[c，ac，bac，abac，babac]，没有相等的前缀和后缀，所有next[5]=0
  • next[6]: ababacb的前缀[a，ab，aba，abab，ababa，ababac]，后缀是[b，cb，acb，bacb，abacb,babacb]，没有相等的前缀和后缀，所有next[6]=0

那么到底该怎么求这个next数组呢？

求next数组就是模式串和自己匹配的过程。

其实有一点可以很容易想到，在求next[j]的时候，我们已经求出了next[0]到next[j-1]了，比如ababacb，

0 1 2 3 4 5 6
p a b a b a c b
next 0 0 1 2

在求next[4]的时候，我们已经求出了next[0..3]，我们知道next[3]=2，也就是说p[0..1]=p[2..3]，那么，要是p[2]=p[4]，next[4]就等于next[3]+1。p[2]也就是p[next[3]]。

0 1 2 3 4 5 6
p a b a b a c b
p a b a b a

求next[4]的时候，不管怎样，我们先将字符串p向右移动2个字符使得p[2]和p[4]对齐，看看p[2]和p[4]是否相等。

让哪个字符和p[4]对其是这么算的，因为知道next[3]=2，p[0..1]=p[2..3]，也就是p[2]应该和p[4]对齐，就是p[next[3]]。

如果相等，next[4]就等于next[3]+1。这里正好相等，所以next[4]=2+1=3。

0 1 2 3 4 5 6
p a b a b a c b
next 0 0 1 2 3

现在求next[5]，不管怎样，我们先将字符串p向右移动2个字符使得p[3]和p[5]对齐，看看p[3]和p[5]是否相等。为什么是p[3]，因为next[4]=3。

0 1 2 3 4 5 6
p a b a b a c b
p a b a b a

这里p[5]不等于p[3]，那怎么办呢，之前说了，求next其实就是模式串的自我匹配，这里匹配不成功，那我们就需要将下面的p进行右移，移动多少个字符，还是要看next数组，因为是p[3]匹配不成功，但是p[0..2]是匹配的，那就右移使得p[next[2]]和p[5]对齐。

0 1 2 3 4 5 6
p a b a b a c b
p a b a

这时p[1]和p[5]对齐，发现p[1]不等于p[5]，我们继续右移，使得p[next[1]]和p[5]对齐。

0 1 2 3 4 5 6
p a b a b a c b
p a b

这时p[0]和p[5]对齐，但p[0]不等于p[5]，此时，我们无法在进行右移了，所以直接让next[5]=0。

0 1 2 3 4 5 6
p a b a b a c b
next 0 0 1 2 3 0

现在求next[6]，因为next[5]=0，所以应该让p[0]和p[6]对齐，看看p[0]是否等于p[6]，不相等，而next[0]=0，所以直接让next[6]=0。

求出next数组之后，KMP算法就算完成一大半了。KMP算法主体和蛮力匹配类似，但是在不匹配的时候文本串不动，移动模式串。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private static int kmp(String text, String pattern) {
   int[] next = next(pattern);
   int j = 0;
   for (int i = 0; i < text.length(); i++) {
       while (true) {
           if (j == pattern.length()) {
               return i - j;
           }
           if (text.charAt(i) == pattern.charAt(j)) {
               j++;
               break;
           } else if (j == 0){
               break;
           } else {
               j = next[j - 1];
           }
       }
   }
   return -1;
}

private static int[] next(String pattern) {
   int[] next = new int[pattern.length()];
   next[0] = 0;
   for (int i = 1; i < pattern.length(); i++) {
       int j = i - 1;
       while (j >= 0) {
           if (pattern.charAt(next[j]) == pattern.charAt(i)) {
               next[i] = next[j] + 1;
               break;
           } else if (next[j] == 0){
               next[i] = 0;
               break;
           } else {
               j = next[j - 1];
           }
       }
   }
   return next;
}