KMP算法模板

#include<cstdio>
#include<cstring>

const int MAXN = 10000 + 10;

void KMP(char *pattern, char *source, int *f){
    //getfail
    int m = strlen(pattern) ,j;
    f[0] = f[1] = 0;
    for(int i = 1; i < m; ++i){
        j = f[i];
        while(j && pattern[i] != pattern[j]) j = f[j];
        f[i+1] = (pattern[i] == pattern[j] ? j + 1 : 0);
    }
    //run
    int n = strlen(source);
    j = 0;
    for(int i = 0; i < n; ++i){
        while(j && source[i] != pattern[j]) j = f[j];
        if(source[i] == pattern[j]) ++j;
        if(j == m) printf("Find at %d\n",i-m+1);
    }
    //print F
    for(int i=0;i<m;++i){
        if(i==0)printf("%d",f[i]);
        else printf(" %d", f[i]);
    }
}

void fcgets(char *data, int n){
    fgets(data, n, stdin);
    char *find = strchr(data, '\n');
    if(find) *find = '\0';
}
char s[MAXN], s2[MAXN];
int f[MAXN];
int main(){
    freopen("KMP.in", "r" ,stdin);
    fcgets(s, MAXN);
    fcgets(s2, MAXN);
    KMP(s2, s, f);
    return 0;
}