P4824 [USACO15FEB] Censoring S
KMP+栈
同样的套路，先找B的最长前后缀，然后与A匹配
不同的是要删除A中的B,特殊的是删除之后可能会产生新的B
那我们可以利用栈的思想，利用f数组，记录A每一位置上B的匹配程度，这样删除时，直接回到上一个匹配程度，以防漏掉。
利用栈记录下标，还在栈内的，说明是没有被删除的，最后统一输出。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int f[N], top, S[N], ne[N];
void get_ne(string s) {
ne[1] = 0;
int n = s.length();
for (int i = 2, j = 0; i <= n; i++) {
while (j && s[i] != s[j + 1]) j = ne[j];
if (s[i] == s[j + 1]) j++;
ne[i] = j;
}
}
int main() {
string s1, s2;
cin >> s1 >> s2;
int n = s1.length(), m = s2.length();
s1 = ' ' + s1;
s2 = ' ' + s2;
get_ne(s2);
for (int i = 1,j=0; i <= n; i++) {
while (j && s1[i] != s2[j + 1]) j = ne[j];
if (s1[i] == s2[j + 1]) j++;
f[i] = j;
S[++top] = i;
if (j == m) {
top -= m;
j=f[S[top]];
}
}
for (int i = 1; i <= top; i++) {
cout << s1[S[i]];
}
return 0;
}