白话分析字符串匹配算法——KMP算法

作者：[e-mail]

博客：blog.focus-linux.net      linuxfocus.blog.chinaunix.net

上次说过要换一种方式去学习算法，这段时间在看《Algorithm In C》，上周正好看完了String Search这一章。先拿这章中介绍的算法来试一下效果吧。

先再重复一下我这次学习算法的一些新想法，以前学算法，总是去学习算法本身的东西，而没有深究为什么算法这样设计，为什么效率高。结果导致学习的效果并不是很好。这次算法学习的过程中，决定好好的想一下这个问题。另外，对于一般开发人员来说，包括我，大部分不是研究型的开发，对于我们来说，重要的不是去通过数学的手段去定量的去证明算法的先进性——关于这一点，估计会有很多人拍砖，这只是我一点拙见，仁者见仁智者见智吧。

毕业这么多年了，数学的东西也基本忘光了，所以下面对于算法的分析，都是大白话，只探求基本原理，并不深究细节。

Knuth-Morris-Pratt 算法，又称KMP算法

主要思想：当patter在某一位置与string匹配失败时，我们除了知道从string的这个位置进行匹配失败这个结果外，是否可以从前面的匹配中获得更多的信息呢。至少还有一个信息，匹配失败前面的字符串，我们已经知道。例如：

abcabcabcdef   --------- string

abcabcdef         --------- pattern

当匹配到第7个字符时，虽然匹配失败了，但是除了这个结果，我们还可以知道string前面的字符串是已经匹配成功了的字符串，即abcabc。而patter本身是abcabcdef，那么就可以知道至少需要向右滑动3个字符，才可能匹配：

abcabcabcdef

     abcabcdef

KMP就是利用已经匹配了的字符串这个信息，来进行尽可能的向右滑动，避免无谓的比较。

那么究竟当不匹配的时候，可以向右滑动多远呢？

以上面的pattern "abcabcdef"为例：

当第一个字符不匹配的时候，没有额外信息，那么就向右滑动1个字符。

当第二个字符不匹配的时候，说明之前匹配的字符为a，但是我们是第二个字符不匹配，还是只能向右滑动1个字符。

当第三个字符不匹配的时候，说明之前匹配的字符为ab，那么可以向右滑动2位；

当第四个字符不匹配的时候，说明之前匹配的字符为abc，那么可以向右滑动3位；

当第五个字符不匹配的时候，说明之前匹配的字符为abca，那么也只能向右滑动3位；

。。。。。。

那么KMP算法的关键问题就是计算pattern某位置匹配失败的时候，可以向右滑动的位数。

下面白话一下如何计算这个滑动位数，0匹配和1匹配时，向右滑动都为1。那么当在第n(n>=2)不匹配时，那么我们可以从偏移1位到m位进行尝试，m最大为n-1。只要0 != strncmp(pattern, pattern+m, n-m-1)，那么就可以继续增加m值。

大致的代码如下：

static void cal_next_table(const char *pattern, int len, int *table)
{
   int i,j;

     /* table[0] 为哨兵 */  

     table[0] = 1;

    for (i = 1; i <= len; ++i) {
        table[i] = table[i-1];
        for (j = table[i]; j < i; ++j) {
            if (0 != strncmp(pattern, pattern+j, i-j-1)) {
                table[i]++;
            }
            else {
                break;
            }
        }
    }
}

通过上面的函数，将生成右移的table表。当第n个不匹配时，可以向右滑动table[n]个字符。

下面是测试代码：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

static void cal_next_table(const char *pattern, int len, int *table)
{
    int i,j;

     table[0] = 1;
    for (i = 1; i <= len; ++i) {
        table[i] = table[i-1];
        for (j = table[i]; j < i; ++j) {
            if (0 != strncmp(pattern, pattern+j, i-j-1)) {
                table[i]++;
            }
            else {
                break;
            }
        }
    }
}


int main()
{
    char pattern[] = "abcabcdef";
    int  table[sizeof(pattern)+1] = {};

    cal_next_table(pattern, sizeof(pattern), table);

    int i;
    printf("%s\n", pattern);

    for (i = 1; i < sizeof(pattern); ++i) {
        printf("%d", table[i]);
    }
    printf("\n");

    return 0;
}

结果如下：

abcabcdef
112333378

最后总结一下，我们从KMP算法中可以获得什么？除了知道这个字符串匹配算法，我们还要争取 获得更多的东西，比如即尽可能的从已经处理过得操作或数据中获得更多的信息。