字符串匹配算法之KMP

た入场券 2022-01-05 10:47 301阅读 0赞

给定两个字符串S、P，如何判断S中包含P？(假设S为较长字符串，要求P中字符在S中要连续出现)

这就是经典的字符串匹配问题。暴力匹配略去不说，一种较好的解法就是KMP。对于一个新手来说，想学习KMP，建议看如下两篇文章：

# [字符串匹配的KMP算法][KMP](阮一峰) #

[从头到尾彻底理解KMP（2014年8月22日版）][KMP_2014_8_22]

如果对第二篇中next数组的讲解不是很懂的话，建议看这篇

# [【经典算法】——KMP，深入讲解next数组的求解][KMP_next] #

本文主要给出kmp的实现：

int getnext(char *p, int next[])
    {
        int len = strlen(p);
        next[0] = -1;
        int k = -1, j = 0;
        while (j < len)
        {
            while (k >= 0 && p[j] != p[k])
            {
                k = next[k];
            }
            k++;
            j++;
            next[j] = k;
        }
        return 0;
    }
    
    void kmp(char *s, char *p)
    {
        int slen = strlen(s);
        int plen = strlen(p);
        int *next = new int[plen + 1];    // size is plen + 1
        getnext(p, next);
        int i = 0, j = 0;
        while (i < slen)
        {
            while (j >= 0 && s[i] != p[j])
            {
                j = next[j];
            }
            i++;
            j++;
            if (j == plen)
            {
                printf("found substring at index: %d\n", i - j);
                j = next[j];    // to find more matches
            }
        }
        delete [] next;    // do not forget
    }

分析：

如果文本串的长度为n，模式串的长度为m，那么匹配过程的时间复杂度为O(n)，算上计算next的O(m)时间，KMP的整体时间复杂度为O(m + n)。

Reference:

# [algorithm to find substring in a string (KMP Algorithm)][algorithm to find substring in a string _KMP Algorithm] #

转载于:https://www.cnblogs.com/gattaca/p/4723530.html

[KMP]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
[KMP_2014_8_22]: http://blog.csdn.net/v_july_v/article/details/7041827
[KMP_next]: http://www.cnblogs.com/c-cloud/p/3224788.html
[algorithm to find substring in a string _KMP Algorithm]: http://tekmarathon.com/2013/05/14/algorithm-to-find-substring-in-a-string-kmp-algorithm/