算法導論-KMP模版

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn = 10001;
int next[maxn];

void Compute(char *p)   //比對串和自己的next值
{
    int m = strlen(p+1);
    memset(next,0,sizeof(next));
    next[1] = 0;
    int k = 0;
    for(int q = 2;q<=m;q++)
    {
        while(k > 0 && p[k+1] != p[q])
        {
            k = next[k];
        }
        if(p[k+1] == p[q])
        {
            k++;
        }
        next[q] = k;
    }
}

void KMP_MATCHER(char *t,char *p)
{
    int n = strlen(t+1);
    int m = strlen(p+1);
    Compute(p);
    int q = 0;
    for(int i=1;i<=n;i++)
    {
        while(q > 0 && p[q + 1] != t[i])  //如果比對不想等那麼比對串就回溯，回溯到記錄的next數組那個位置
        {
            q = next[q];
        }
        if(p[q+1] == t[i])  //如果比對成功就比對下一個位置
        {
            q++;
        }
        if(q == m)  //已經成功比對
        {
            cout<<"matching complete!shift:"<<i-m<<endl;  //如果比對成功輸出并傳回總共移動了幾個位置
            q = next[q];
        }
    }
}

int main()
{
    char str1[maxn];
    char str2[maxn];
    int i;
    scanf("%s%s",str1+1,str2+1);
    KMP_MATCHER(str1,str2);
    return 0;
}