KMP算法

#include <cstdio>
#include <cstring>
const int MAXN = 10005;
int next[MAXN], len1, len2;//next[i]表示子串[0~i]的前缀同时也是该子串的后缀的最长真前缀（proper prefix）长度 
char t[MAXN], p[MAXN];//t为主串，p为模式串 
void make_next() {//构建next数组 
    next[0] = 0;
    for (int i = 1, j = 0; i < len2; i++) { 
        while (j > 0 && p[j] != p[i]) { 
            j = next[j - 1];
        }
        if (p[j] == p[i]) {
            j++;
        }
        next[i] = j;
    }
}
int kmp() { 
    make_next();
    for (int i = 0, j = 0; i < len1; i++) {
        while (j > 0 && t[i] != p[j]) {
            j = next[j - 1];
        }
        if (t[i] == p[j]) {
            j++;
        }
        if (j == len2) {
            return i - j + 1;
        }
    }
}
int main() {
    scanf("%s %s", t, p);
    len1 = strlen(t), len2 = strlen(p);
    make_next();
    /*for (int i = 0 ; i < len; i++) {
        printf("%d ", next[i]);
    }*/
    printf("%d", kmp());
    return 0;
}