KMP(Knuth–Morris–Pratt) 算法

题目

给定两个字符串S和W，长度分别是N和M。实现一个算法判断W是否在S中出现，如果是则返回W在S中的开始位置，否则返回-1。

暴力解法

如果采用暴力求解，需要遍历S中的字符，然后再从每一个位置遍历W，看是否能够匹配，比如：

1
2


S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD

从S[0]出发，到W[3]=D发现不匹配，再从S[1]出发进行同样的操作，因为每次遍历到一个字符时，匹配过程相当于从头开始，之前的检查结果并不能优化当前的检查，所以暴力解法的时间复杂度是O(N×M)。

KMP算法

如果我们能够在进行某一步匹配检查的时候利用之前的检查结果，就会提升效率。KMP算法的思想就是：W本身就包含了足够的信息可以在发生错配时来确定下一个匹配的起点，我们可以利用它绕过对先前匹配的字符的重新检查。

搜索过程

我们还是用之前的S和W作为例子，来看看KMP是怎么工作的，首先我们需要两个数值：

m: 表示S内W的预期匹配开始的位置
i: 表示W中当前考虑的字符的索引

在每一步中，先比较S[m+i]和W[i]，如果两者相等，则给i加1，比如：

1
2
3
4


m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

初始m=0, i=0，逐步递增i，在第四次比较S[3] = ''与W[3] = 'D'时不匹配，这时算法不是从S[1]开始重新搜索，而是注意到S中的位置1和2之间没有出现’A’，即它们都不匹配W中的第一个字符，因此，算法设置m=3，i=0：

1
2
3
4


m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:    ABCDABD
i:    0123456

这时第一个字符匹配失败，则设置m = 4，i = 0：

1
2
3
4


m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

这次，匹配几乎成功，直到i=6，在W[6]和S[10]处出现了不匹配。然而，就在当前部分匹配结束之前，有一个子串W[4..5] // "AB")可能是一个新匹配的开始，所以算法必须考虑到这一点。这时我们不能继续往下走，而是要从当前匹配失败的地方往回走两个位置，算法设置m=8（初始前缀的开始）和i=2（表示前两个字符匹配），继续匹配。因此，算法略过了之前匹配的"AB"字符：

1
2
3
4


m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

当m=8, i=2时，由于W[2](‘C’)与S[10](’ ‘)不匹配，在新位置的搜索立即失败。与第一次试验一样，不匹配导致算法返回到W的开头，并在S的不匹配字符位置开始搜索：m = 10，i = 0。而S[10](’ ‘)与W[0]依旧不匹配，这时继续设置m=11, i=0：

1
2
3
4


m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

和之前一样，S[17]和W[6]不匹配，又有"AB”，所以此时设置m = 15, i=2：

1
2
3
4


m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

这次匹配成功，我们得到了需要的结果：15。

局部匹配表（Partial match table）

上边的过程是不完整的，我们回头看一下m = 4，i = 0时的情况。

1
2
3
4


m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

由于S[10]和W[6]不匹配，而且因为匹配的末尾是"AB"，我们需要设置m=8, i=2，现在需要解决的就是怎么知道要这样设置呢？先来观察一下W:

1

ABCDABD

这里我们遍历到了W[6]，而匹配的末尾是"AB"，我们可以发现W的头两个字符也是"AB"，正是由于这个重合，我们才需要将m设置成8，退回两个位置从可以匹配W开头的地方重新开始，

也就是说，对于W中的任意位置i，我们需要找到一个位置j(0<j < i)，该位置到i-1的这段字符串正好和W的开头相同，我们需要找到j的最小值，也就是匹配的最大长度，这个长度就是我们在寻找下一个匹配时必须回溯的距离。由于我们需要对W中的每个i都找到这样一个最大长度，所以可以把它们存到一个数组里，我们把这个数组称为T: Partial match table。

因此，T[i]代表W的初始段和以W[i - 1]结束的子串的最大重合长度，我们使用的惯例是空字符串的长度为0，另外由于W[0]之前没有字符，我们设T[0] = -1。

比如W="AAAAB”，此时T[4]应该是多少？在T[4]之前的子串是"AAAA”，又由于0 < j < i（如果j=0，我们有可能陷入死循环，比如现在这个例子），所以这个字符串的后缀子串和前缀子串的最大匹配为"AAA”，即T[4] = 3。

创建partial match table

首先T[0]=-1，由于W[0]和W[1]之间并没有字符，所以T[1]=0，其余元素的运算需要用到动态规划的思想。

假设我们现在需要计算T[i]，那么T[i-1]和之前的元素都已经计算过了，我们就要利用这些计算过的元素（下边W中的A, B和C代表的是变量，而不是具体的字符）：

1
2
3


        b    i-1  i
W: [... B ... C  ...]
T: [... a ... b  ...]

假设T[i-1]==b，说明W[0..(b-1)]==W[(i-b-1)..(i-2)]，此时需要看W[b]和W[i-1]是否相等。

若W[b]==W[i-1]，那么T[i]相当于在T[i-1]的基础上又多了一个字符，即:

T[i]=T[i-1]+1

若W[b]!=W[i-1]，则还需要继续往前找：

1
2
3


        a     b      i-1  i
W: [... A ... B  ...  C ...]
T: [... x ... a  ...  b ...]

前边根据T[i-1]==b可以得到 W[0..(b-1)]==W[(i-b-1)..(i-2)]

假设T[b]==a，则：W[0..(a-1)]==W[(b-a)..(b-1)]

1
2
3
4
5
6


    
|<------------- b1 ------------->| |<------------- b2 ------------->|
[0            ...           (b-1)] [(i-b-1)       ...          (i-2)]
    
[0   ..   (a-1)]..[(b-a) .. (b-1)]                   [(i-a-1)..(i-2)]
|<---- a1 ---->|  |<---- a2 ---->|                   |<---- a3 ---->|

从上边的包含关系中可以得到：

1
2
3
4
5


b1 == b2
   ↓
a2 == a3 ↘ 
           → a1 == a3 → W[0..(a-1)] == W[(i-a-1)..(i-2)]
a1 == a2 ↗ 

此时如果W[a]==W[i-1]，则：

T[i-1]=T[b]+1=a+1

否则继续循环操作

如果一直向前跳到了最左边，由于T[0]==-1，前边不再有匹配的字符，则T[i-1]=0。

有兴趣可以分析一下上边的过程的时间复杂度，它是O(M)。

代码实现

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


class KMP {
  public int matchStr(String str, String match) {
    if (match == null || match.length() < 1) {
      return 0;
    }

    if (str == null || str.length() < 1) {
      return -1;
    }

    if (match.length() > str.length()) {
      return -1;
    }

    char[] ss = str.toCharArray();
    char[] ms = match.toCharArray();
    int[] table = getPartialTable(ms);

    int m = 0, i = 0;
    while (m < ss.length && i < ms.length) {
      if (m + i >= ss.length) {
        return -1;          
      } else if (ss[m + i] == ms[i]) {
        i++;
      } else {
        m = m + i - table[i];
        i = table[i] == -1 ? 0 : table[i];
      }
    }

    return i == ms.length ? m : -1;
  }

  private int[] getPartialTable(char[] ms) {
    int length = ms.length;
    if (length == 1) {
      return new int[] { -1 };
    }

    int[] table = new int[length];
    table[0] = -1;
    table[1] = 0;

    int i = 2, j = 0;
    while (i < length) {
      if (ms[i - 1] == ms[j]) {
        table[i++] = ++j;
      } else if (j > 0) {
        j = table[j];
      } else {
        table[i++] = 0;
      }
    }
    return table;
  }
}

Conclusion

KMP是匹配字符串的算法，相似的还有 Sunday，BM，Horspool算法。KMP的主要思路是在某一步匹配的时候利用之前的匹配结果，而这需要用一个记录了最大前后匹配数量的table，构建table的过程也是一个利用之前操作记录的动态规划过程。

文章目录

题目