KMP


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

void init(char T[], int l, int next[]) {
    int i=0, j=-1;
    next[0]=-1;
    while(i<=l) {
        if(j==-1 || T[i]==T[j]) {
            next[++i]=++j;
        }else{
            j=next[j];
        }
    }
}

int findcount(char S[], int L, char T[], int l, int next[]) {
    int i=0, j=0, count=0;
    while(i<L) {
        if(j==-1 || S[i]==T[j]) {
            ++i; ++j;
            if(j==l) {
                ++count;
                j=next[j];
            }
        }else{
            j=next[j];
        }
    }
    return count;
}
int find(char S[], int L, char T[], int l, int next[]) {
    int i=0, j=0;
    while(i<L) {
        if(j==-1 || S[i]==T[j]) {
            ++i; ++j;
            if(j==l) return i-l;
        }else{
            j=next[j];
        }
    }
    return -1;
}
void compare(char S[], int L, char T[], int l) {
    printf("compare S and T\n");
    printf("        ");
    for(int i=0;i!=L;++i) printf("%d", i%10);
    printf("\n    S: |%s|\n", S);
    for(int i=0;i<=L-l;++i) {
        printf("    T: |");
        for(int j=0;j!=i;++j) printf(" ");
        printf("%s", T);
        for(int j=i+l;j!=L;++j) printf(" ");
        printf("|\n");
    }
    printf("\n");
}
void print(int next[], int l) {
    printf("print next\n");
    printf("          ");
    for(int i=0;i<=l;++i) printf("%3d", i);
    printf("\n    next: ");
    for(int i=0;i<=l;++i) printf("%3d", next[i]);
    printf("\n");
    printf("\n");
}
int main() {
    // char S[100] = "abababababab";
    // char T[10] = "ababab";
    // char S[100] = "abcabcdabcabcd";
    // char T[10] = "abcd";
    char S[100] = "aaaaaaaaaaaa";
    char T[100] = "aaaaa";
    int L=strlen(S), l=strlen(T);
    compare(S, L, T, l);
    int next[10];
    init(T, l, next);
    print(next, l);
    printf("find: ");
    for(int i=0,j=0;i<=L;i=i+j+1) {
        j=find(S+i, L, T, l, next);
        if(j==-1) break;
        printf("%d, ", i+j);
    }
    printf("-1\n");
    printf("findcount: %d\n", findcount(S, L, T, l, next));
    return 0;
}