一个 xmlns called ring length using inpu ted
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.
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⋅106
, w,p
consists of only lowercase letter)
For each test, write 1
string which denotes the censored text.
- abc
- aaabcbc
- b
- bbb
- abc
- ab
- a
- ab分析:每次删第一个模板串,删掉后重复这个操作,问最后剩下的串;kmp可以找到模板串,关键是删掉后怎么回溯;直接记录答案数组,删掉模板串相当于下标-len,这样就能轻松回溯;比赛时居然傻傻地记录最长已删长度,然后回溯,真是太蠢了。。。代码:
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include <string>
- #include <set>
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #definerep(i,m,n) for(i=m;i<=n;i++)#definemod 1000000009#defineinf 0x3f3f3f3f#definevi vector
- #definepb push_back#definemp make_pair#definefi first#definese second#definell long long#definepi acos(-1.0)#definepii pair
- #definesys system("pause")const intmaxn=5e6+10;
- const intN=2e5+10;
- using namespace std;
- ll gcd(ll p,ll q){returnq==0p:gcd(q,p%q);}
- ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}
- int n,m,k,t,dp[maxn],nxt[maxn];
- char a[maxn],b[maxn],ret[maxn];
- int main()
- {
- int i,j;
- while(~scanf("%s%s",a,b))
- {
- intlen=strlen(a);
- nxt[0]=j=-1;
- i=0;
- while(a[i])
- {
- while(!(j==-1||a[i]==a[j]))j=nxt[j];
- nxt[++i]=++j;
- }
- i=j=k=0;
- while(b[i])
- {
- ret[++k]=b[i];
- while(!(j==-1||b[i]==a[j]))j=nxt[j];
- ++i,++j;
- dp[k]=j;
- if(j==len)
- {
- k-=len;
- j=dp[k];
- }
- }
- ret[++k]=0;
- printf("%s\n",ret+1);
- }
- return 0;
- }
SCU Censor
来源: http://www.bubuko.com/infodetail-2048506.html