首页 > 代码库 > KMP算法的基本实现,C++

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

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++