KMP算法

众所周知,KMP 算法的作用是匹配字符串,比如在一个文本编辑器中查找符合某一模式的所有字符等。

就我认为,这个算法还是比较难的,反正我是看了好长时间都没懂,哈哈~

今天看了《算法导论》中关于该算法的部分,对求 next 数组部分不是特别理解,参考了网上的某些文章(地址已失效),他这篇文章的分析确实不错,但代码部分有些缺陷,我已改正过来。

简要记录如下:

普通的暴力匹配算法是将模式串和文本串中的每一个可能的位置都进行逐个比较,假设文本串长度为 n,模式串长度为 m,那么它的时间复杂度就是 O(mn)。其缺点是如果模式串中有重复的字符,并没有很好地利用之前比较过的信息,导致做了一些不必要的比较操作。

而 KMP 算法则是有一个称之为 next 的数组,该数组记录了模式串中从开始到当前位置前一个的子串中可以匹配的最大前缀和后缀的长度。有点绕口是吧?来看一个例子:

假设我们有字符串string str=“ABABABC",则 next 数组长度为str.size()==7。那么:

而如何用代码求出 next 数组,我认为这是 KMP 算法的一个难点。具体如下。

//暴力匹配
void NaiveStringMatcher(const string& text, const string& pattern)
{
    int n = text.size();
    int m = pattern.size();
    int i;
    int s;
    for (s = 0;s <= n - m;++s)
    {
        for (i = 0;i < m;++i)
        {
            if (text[s + i] != pattern[i])
                break;
        }
        if (i == m)
            cout << "Pattern occurs with shift " << s << endl;
    }
}

void CalcNext(vector<int>& next, const string& p)
{
    int length = p.size();
    next.resize(length);
    next[0] = -1;
    int k = -1, j = 0;
    while(j < length-1)
    {
        while (k >= 0 && p[j] != p[k])
            k = next[k];
        k++;
        j++;
        next[j] = k;
    }
}

void KMP(const string& text, const string& pattern)
{
    int tlen = text.size();
    int plen = pattern.size();
    vector<int> next;
    CalcNext(next, pattern);
    int i, j=0;
    for (i = 0;i < tlen;++i)
    {
        while (j > 0 && text[i] != pattern[j])
            j = next[j];
        if (text[i] == pattern[j])
            j++;
        if (j == plen)
        {
            cout << "Pattern occurs with shift " << i - plen + 1 << endl;
            j = next[j-1];
        }
    }
}

github地址在这里