数据结构和算法

字符串匹配算法（三）——KMP算法

KMP算法是常用的字符串匹配算法之一，是由Knuth、Pratt和Morris发明的。其中Knuth就是著名科学家Donald Knuth。

该算法可以在O(n+m)的时间数量级上完成模式匹配操作。与传统算法相比其改进在于每当一趟匹配过程中出现比较不相等时不用回溯目标字符串。

这个算法还是比较难理解，下面通过一个例子来讲解。
有一个目标字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？

1).

BBC ABCDAB ABCDABCDABDE
ABCDABD
首先目标字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与源字符串”ABCDABD”的第一个字符相比，不匹配，则目标字符串后移一位。 2). 
BBC ABCDAB ABCDABCDABDE
 ABCDABD
B与A不匹配，再次后移。 3). 
BBC ABCDAB ABCDABCDABDE
    ABCDABD
就这样直到有一个字符相同为止。 4). 
BBC ABCDAB ABCDABCDABDE
    ABCDABD
接着比较下一个字符，还是相同的。再继续。 5). 
BBC ABCDAB ABCDABCDABDE
    ABCDABD
这时又出现了字符不匹配的情况，如果是传统的算法的话就把目标字符串进行回溯，源字符串后移一位。变成如下情形： 
BBC ABCDAB ABCDABCDABDE
     ABCDABD
毕竟这也是最容易理解的，但是这样一来很多字符又需要再重新比较一次。因此效率比较低。 6). 虽然D与空格不匹配，但是前面的ABCDAB是相匹配的。KMP算法就是利用这个已知信息，不要把“搜索”位置称回已经比较过的位置，而且继续比较之后的，这样就减少了重复的比较，提高了效率。继续向后移动变成如下情形： 
BBC ABCDAB ABCDABCDABDE
        ABCDABD

这个移动过程需要一张部分匹配表：

j        1234567
源字符串 ABCDABD
next[j]  0111123
因为前6个字符是匹配的，最后一个匹配的字符B对应next值为2,根据公式： 移动位数=已匹配字符数-对应的next值 因此将源字符串后移6-2=4位。 7).因为空格与C不相同，继续后移。 
BBC ABCDAB ABCDABCDABDE
          ABCDABD

8).空格与A不相同，继续重复之前的操作进行后移。

BBC ABCDAB ABCDABCDABDE
           ABCDABD

9).这里C与D不相同，继续用之前的方法进行后移。

BBC ABCDAB ABCDABCDABDE
               ABCDABD
最后匹配完成，字符串”BBC ABCDAB ABCDABCDABDE”里面包含字符串”ABCDABD”。 下面介绍一下部分匹配表的计算方法。 公式为： next[j] = 0 (j=1) next[j] = Max {k 1<k<j 且 'p(1)...p(k-1)' = 'p(j-k+1)...p(j-1)'} (当此集合不为空时) next[j] = 1 (其他情况) 然后根据公式讲解一下上面例子中的字符串的部分匹配表的计算。(注：这里讲解时是按照数组下标从1开始的，而在C语言中是从0开始的) 
j        1234567
源字符串 ABCDABD

由公式得next[1] = 0， next[2] = 1， next[3] = 1， next[4] = 1， next[5] = 1。
当j=6时，p[1]=p5 => k=2 => next[6] = 2。
当j=7时，p[1:2]=p5:6 => k=3 => next[7] = 3。

用C语言实现如下：

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
#include <stdio.h>

// KMP算法的重点就是求next函数值
void make_next(const char *pattern, int len, unsigned int *next)
{
    int i=1, j=0;
    next[1] = 0;

    while (i <= len) {
        if (j == 0 || pattern[i-1] == pattern[j-1]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int kmp_match(char *t, char *p, int next[], int len1, int len2)
{
    int i=0, j=0;
    while (i < len1 && j < len2) {
        if (j == 0 || t[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j >= len2 ) return i - len2;
    return -1;
}

int main(int argc, char *argv[])
{
    char t[] = "BBC ABCDAB ABCDABCDABDE";
    char p[] = "ABCDABD";
    printf("t: %s\np: %s\n", t, p);
    int len = sizeof(p);
    int next[len];
    make_next(p, len-1, next);
    int i;
    for (i=1; i<len; i++) {
        printf("%4d", next[i]);
    }
    printf("\n");
    printf("index: %d\n", kmp_match(t, p, next, sizeof(t)-1, len-1));
    return 0;
}