KMP 字符串匹配 题解中

西B105课程会议

点击链接，即可看见教师的屏幕共享，每60分钟会退出重进

https://teams.live.com/meet/9317892917873?p=8OPYYLkeZCe47rFZ8v

KMP算法

关键词：文本串、模式串、最长公共前后缀

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
char S[N], T[N];
int ne[N];

void kmp(char* s, char* p) {
    int ls = strlen(s + 1), lt = strlen(p + 1);
    for (int i = 2, j = 0; i <= lt; i++) {
        while (j && p[i] != p[j + 1])
            j = ne[j];
        if (p[i] == p[j + 1])
            j++;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= ls; i++) {
        while (j && s[i] != p[j + 1])
            j = ne[j];
        if (s[i] == p[j + 1])
            j++;
        if (j == lt) {
            cout << i - lt + 1 << endl;
            j = ne[j];
        }
    }
    for (int i = 1; i <= lt; i++)
        cout << ne[i] << " \n"[i == lt];
}
int main(int argc, char* argv[]) {
    cin >> S + 1 >> T + 1;
    kmp(S, T);
    return 0;
}