kmp算法c++

kmp算法通过next数组使查找失败时减少跳转后比较的次数来优化字符串查找，next数组存储了前缀和后缀相同的位置信息，类似动规，可以存储查找数组的信息来防止重复查找，最终复杂度可以达到O（n+m）。

以t=“abcabd”字符串为例进行讲解

next数组存储的是当前位置与前面具有相同前缀的长度，同时在查找失败后，可以在失败位置的其哪一个位置对应的next数组值来跳转到具有相同前缀的字符串的下一个位置，这样就可以避免重复验证前缀部分是否和被查找的字符串匹配。

具体的演示可以看和手算方法见「六分钟速通」KMP算法求解流程，up讲的简单明了。视频里pm即为文中的next数组

next[i]里的数字代表包括t[i]在内的部分与前面字符串部分子串相同的长度，同时该数字也是前面相同子串的下一个字符的下标。

这里设j，k作为下标表示，j为当前计算的下标，k为前面与当前计算下标j结尾的子串相同的子串的结尾下标，即具有相同前缀的子串结尾下标。

当k=0时，有两种情况，一是t[j]=t[k],那么此时next[j]=next[j-1]+1，即相同前缀部分变大，如果不同，此时k=0，则next[j]应该为0，即没有相同前缀。

当k!=0时，如果t[k]=t[j],则按上述计算方法来表示扩大相同前缀，如果t[k]!=t[j]，那么向前找相同前缀，做法时k=next[k-1],因为next数组存储的是当前位置与前面具有相同前缀的长度，则向前查找只需要找到以k-1结尾的相同子串的长度，如果还不同，重复向前查找，直到k=0或找到相同前缀为止。

#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;

void grtnext(char *c, int *nextKMP)
{
    int len = strlen(c);

    nextKMP[0] = 0;
    int k = 0;
    int j = 1;
    while (j < len)
    {
        if (k == 0)
        {
            if (c[j] == c[k])
            {
                nextKMP[j] = 1;
                k++;
            }
            else
                nextKMP[j] = 0;
            j++;
            continue;
        }
        if (c[j] == c[k])
        {
            nextKMP[j] = nextKMP[j - 1] + 1;
            k++;
            j++;
        }
        else
        {
            k = nextKMP[k - 1];
        }
    }
}
int KMP(char *s, char *t, int *next, int *re)
{
    int lens = strlen(s);
    int lent = strlen(t);
    int i = 0, j = 0;

    while (i < lens && j < lent)
    {
        re[0]++;
        if (s[i] == t[j])
        {
            i++;
            j++;
        }
        else
        {
            if (j == 0)
                i++;
            else
                j = next[j - 1];
        }
    }
    if (j == lent)
        return i - lent;
    return -1;
}
int trlen(char *s)
{
    int len = 0;
    while (s[len] != '\0')
    {
        len++;
    }
}
int main()
{
    char *c = "aabaac";
    char *s = "aabaabaaac";
    int len = strlen(c);
    int re[2] = {0};
    int *nextKMP = new int[len];
    grtnext(c, nextKMP);
    int k = KMP(s, c, nextKMP, re);
    // for (int i = 0; i < len; i++)
    // {
    //     cout << nextKMP[i] << " ";
    // }
if(k==-1)cout<<"no find"<<endl;
else
    cout << k + 1 << endl;
    cout << re[0]; // 输出比较次数
    system("pause");
}