《資訊奧賽一本通》-刷題記錄

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

const int N = 1e6 + 10;

char  s[N], p[N];
int ne[N];
int stk[N], f[N], top;
int main () {
    cin >> s + 1 >> p + 1;
    int n = strlen (s + 1), m = strlen (p + 1);
    for (int i = 2, j = 0; i <= m; i ++) {
        while (j && p[j + 1] != p[i]) j = ne[j];
        if (p[j + 1] == p[i]) j ++;
        ne[i] = j;
    }
    
         for (int i = 1, j = 0; i <= n; i ++) {
            while (j && s[i] != p[j + 1]) j = ne[j];
            if (s[i] == p[j + 1]) j ++;
             f[i] = j;
             stk[++top] = i;
            if (j == m) {
                top -= m;
                j =  f[stk[top]];
            }
        }
   
   for (int i = 1; i <= top; i ++) 
               cout << s[stk[i]];
 
    return 0;
}
如何實作kmp删除字串？用棧記錄每一個模闆串的下标，然後用一個數組記錄f[i] = j，記錄一個下标對應的比對串比對到的位置。如果j=m表示比對成功，然後在棧中删除對應數量的下标，并把j重新定位到新的棧頂元素對應的比對串比對到的位置。