BZOJ3942 [Usaco2015 Feb]Censoring

维护一个栈。。。如果栈顶出现了要被删除的字符串就全删掉就好了,判断的话。。。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纪念~)

上一篇:iOS开发-- RunLoop的基本概念与例子分析


下一篇:Loadrunner:error -86401 Failed to connceted xxx.xxx.xxx.xxx:25问题解决