首页 > 代码库 > SCU Censor

SCU Censor

2024-09-18 15:27:50   225人阅读

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


联系
我们