KMP算法的基本实现，C++

浏览数：82 / 时间：2015年06月08日

KMP算法的实现，基于算法导论32.4节。

int* generateNext(string &p)
{
    const int m = p.length();
    int *next = new int[m];
    int k = -1;
    next[0] = -1;
    for (int i = 1; i < m; i++)
    {
        while (k>-1 && p[k + 1] != p[i])
            k = next[k];
        if (p[k + 1] == p[i])
            k++;
        next[i] = k;
    }
    return next;
}

void KMP_Matching(string&p, string&t)
{
    const int m = p.length();
    const int n = t.length();
    int *next = generateNext(p);
    int k = -1;
    for (int i = 0; i < n; i++)
    {
        while (k>-1 && p[k + 1] != t[i])
            k = next[k];
        if (p[k + 1] == t[i])
            k++;
        if (k == m - 1)
        {
            cout << "Found it at " << i - k << endl;
            k = next[k];
        }
    }
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

KMP算法的基本实现，C++