首页 > 代码库 > SCU Censor
SCU Censor
Censor
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⋅106
, 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 ab
Sample Output
a ab
分析:每次删第一个模板串,删掉后重复这个操作,问最后剩下的串;
kmp可以找到模板串,关键是删掉后怎么回溯;
直接记录答案数组,删掉模板串相当于下标-len,这样就能轻松回溯;
比赛时居然傻傻地记录最长已删长度,然后回溯,真是太蠢了。。。
代码:
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <bitset>#include <map>#include <queue>#include <stack>#include <vector>#include <cassert>#include <ctime>#define rep(i,m,n) for(i=m;i<=n;i++)#define mod 1000000009#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define sys system("pause")const int maxn=5e6+10;const int N=2e5+10;using namespace std;ll gcd(ll p,ll q){return q==0?p: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)) { int len=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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。