维护一个栈。。。如果栈顶出现了要被删除的字符串就全删掉就好了,判断的话。。。kmp就行了
/**************************************************************
Problem: 3942
User: rausen
Language: C++
Result: Accepted
Time:224 ms
Memory:11548 kb
****************************************************************/ #include <cstdio>
#include <cstring> using namespace std;
const int N = 1e6 + ; char s1[N], s2[N], s[N];
int next[N], a[N], top; int main() {
int i, j, len;
gets(s1 + ), gets(s2 + );
len = strlen(s2 + );
for (i = , j = next[] = ; s2[i]; ++i) {
while (j && s2[i] != s2[j + ]) j = next[j];
if (s2[i] == s2[j + ]) ++j;
next[i] = j;
}
for (i = ; s1[i]; ++i) {
j = a[top], s[++top] = s1[i];
while (j && s2[j + ] != s[top]) j = next[j];
if (s[top] == s2[j + ]) ++j;
a[top] = j;
if (a[top] == len) top -= len;
}
s[top + ] = '\0';
puts(s + );
return ;
}
(p.s. AC600纪念~)