维护一个栈。。。如果栈顶出现了要被删除的字符串就全删掉就好了，判断的话。。。kmp就行了
1 /************************************************************** 2 Problem: 3942 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:224 ms 7 Memory:11548 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 13 using namespace std; 14 const int N = 1e6 + 5; 15 16 char s1[N], s2[N], s[N]; 17 int next[N], a[N], top; 18 19 int main() { 20 int i, j, len; 21 gets(s1 + 1), gets(s2 + 1); 22 len = strlen(s2 + 1); 23 for (i = 2, j = next[1] = 0; s2[i]; ++i) { 24 while (j && s2[i] != s2[j + 1]) j = next[j]; 25 if (s2[i] == s2[j + 1]) ++j; 26 next[i] = j; 27 } 28 for (i = 1; s1[i]; ++i) { 29 j = a[top], s[++top] = s1[i]; 30 while (j && s2[j + 1] != s[top]) j = next[j]; 31 if (s[top] == s2[j + 1]) ++j; 32 a[top] = j; 33 if (a[top] == len) top -= len; 34 } 35 s[top + 1] = ' '; 36 puts(s + 1); 37 return 0; 38 }
(p.s. AC600纪念~)