Censor SCU - 4438
frog is now a editor to censor so-called sensitive words (敏感词).
She has a long text (p). Her job is relatively simple -- just to find the first occurence of sensitive word (w) and remove it.
frog repeats over and over again. Help her do the tedious work.
Input
The input consists of multiple tests. For each test:
The first line contains (1) string (w). The second line contains (1) string (p).
((1 <={length of}w, p <= 5 * 10^6), (w, p) consists of only lowercase letter)
Output
For each test, write (1) string which denotes the censored text.
Sample Input
abc
aaabcbc
b
bbb
abc
abSample Output
a
abKMP还是比较难呀，更何况是KMP变形，想了好久。。
// Asimple #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <queue> #include <vector> #include <string> #include <cstring> #include <stack> #include <set> #include <map> #include <cmath> #define INF 0x3f3f3f3f #define mod 1000000007 #define debug(a) cout<<#a<<" = "<<a<<endl using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 5000000+5; ll n, m, T, len, cnt, num, ans, Max, k; char str[maxn], s[maxn]; int Next[maxn], pre[maxn]; void getNext() { int j,k; j=0; k=-1; Next[0]=-1; while(j<cnt) { if(k==-1||s[j]==s[k]) Next[++j]=++k; else k=Next[k]; } } void KMP() { getNext(); int i,j=0, k = 0; char a[maxn]; for(i=0; i<len; i++, k++) { a[k] = str[i]; while(j>0&&str[i]!=s[j]) j=Next[j]; if( s[j]==str[i] ) j++; if(j==cnt) { k -= cnt; j=pre[k]; } pre[k] = j; a[k+1] = '\0'; } printf("%s\n", a); } void input() { while( ~scanf("%s%s", s, str) ) { cnt = strlen(s); len = strlen(str); KMP(); } } int main() { input(); return 0; }
