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

2518 人浏览 | 时间: 2015-10-15 23:02:02 | 作者: 烫烫烫烫烫烫烫烫
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算法中可以获得什么?除了知道这个字符串匹配算法,我们还要争取 获得更多的东西,比如即尽可能的从已经处理过得操作或数据中获得更多的信息。


相关阅读