KMP

这可太搞心态了

「天勤公开课」KMP算法易懂版

王道计算机考研 KMP算法

算法：next数组的求法详解

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;
int n, m;
char target[N];
char source[N];

// nex[1] = 0, nex[2] = 1;
int nex[N] = {0, 0, 1};

void printNext() {
    for (int i = 1; i <= n; ++ i) {
        cout << nex[i] << " ";
    }
    cout << endl;
}

int main() {
    

    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> target[i];
    cin >> m;
    for (int i = 1; i <= m; ++ i) cin >> source[i];

    // get next array
    for (int cut = 3; cut <= n; ++ cut) {
        int pre = cut - 1, val = cut - 1;
        while (val && target[pre] != target[nex[val]]) {
            val = nex[val];
        }
        nex[cut] = nex[val] + 1;
    }

    // get result
    for (int s = 1, t = 1; s <= m; s ++) {
        while(t != 1&& source[s] != target[t]) t = nex[t];
        if (source[s] == target[t]) t ++;
        
        if (t - 1 == n) {
            printf("%d ", s - t + 1);
            t = nex[t - 1];
            s --;
        }
    }

    return 0;
}

/*
12
ABABAAABABAA

target: ABABAAABABAA
next:   011234223456
*/