KMP

#include <iostream>
#include <string.h>
using namespace std;
int Next[1110];
void get_Next(char *p){
    int m = strlen(p);
    Next[0] = Next[1] = 0;
    for (int i=1; i<m; ++i){
        int j=Next[i];
        while(j&&p[i]!=p[j]){
            j = Next[j];
        }
        Next[i+1] = p[i]==p[j]?j+1:0;
    }
}
int kmp (char *T, char *s){
    int n=strlen(T), m = strlen(s);
    get_Next(s);
    int j=0;
    for (int i=0; i<n; ++i){
        while(j && T[i]!=s[j]){
            j = Next[j];
        }
        if(s[j]==T[i]){
            ++j;
        }
        if(j==m){
            return i-m+1;
        }
    }
    return -1;
}
int main() {
    char s[1100], T[1100];
    cin >> T >> s;
    cout << kmp(T,s) << endl;
    return 0;
}

扩展KMP

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

const int maxn = 1100;
int Next[maxn],extend[maxn];

void get_Next(char *s)
{
    int n = strlen(s);
    int i,j,k;
    for( j=0 ;1+j<n && s[j]==s[1+j];++j);
        Next[1] = j;
        k=1;
        for(i=2;i<n;++i)
        {
             int len = k + Next[k] , L = Next[i-k];
            if(L<len-i)
            {
                Next[i] = L;
            }else {
                for(j=max(0,len-i);i+j<n && s[j]==s[i+j];++j);
                    Next[i]=j;
                k=i;
            }
        }
    Next[0] = n;
}
void ex_kmp(char *T,char *s)
{
    int n = strlen(T),m = strlen(s);
    int i,j,k;
    for(j=0;j<n && j<m && T[j]==s[j];++j);
    extend[0]=j;
    k=0;
    for(i=1;i<n;++i)
    {
        int len = k+extend[k],L=Next[i-k];
        if(L<len-i)
        {
            extend[i] = L;
        }else
        {
            for(j=max(0,len-i);j<m && i+j<n && s[j]==T[i+j];++j);
            extend[i] = j;
            k = i;
        }
    }
}
int main() {
    char s[maxn],T[maxn];
    cin>>T>>s;
    get_Next(s);
    ex_kmp(T,s);
    for(int i=0;i<strlen(T);++i)
    {
        cout<<extend[i]<<" ";
    }
    cout<<endl;
    return 0;
}