Censoring

Time Limit: 10 Sec Memory Limit: 128 MB

Description

有一个S串和一个T串，长度均小于1,000,000，设当前串为U串，然后从前往后枚举S串一个字符一个字符往U串里添加，若U串后缀为T，则去掉这个后缀继续流程。

Input

第一行是S串，第二行是T串。

Output

输出一行，表示按照操作后得到的串。

Sample Input

whatthemomooofun
　moo

Sample Output

whatthefun

HINT

串长小于1000000。

Main idea

按照S串的顺序加入S串中的字符，一旦出现了一段和T串一样，则删去这一段，求最后得到的串。

Solution

运用KMP，我们显然只要先把T串加入到Stack里面，然后再按照S的顺序加入字符，每次求next（next[i]表示s[1…i]中最长的公共前后缀），显然next==T串长度的话删去相应长度即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<bitset>
using namespace std;

const int ONE=2000001;

int n,m;
char a[ONE],b[ONE],Stack[ONE];
int next[ONE],j,top;

int get()
{
        int res=1,Q=1;char c;
        while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
        res=c-48;
        while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
        return res*Q;
}

void Deal(int n,char a[],int PD)
{
        for(int i=PD;i<=n;i++)
        {
            Stack[++top] = a[i];
            j=next[top-1];
            while(j && Stack[j+1] != Stack[top]) j=next[j];
            if(Stack[j+1] == Stack[top]) j++;
            next[top] = j;
            if(PD==1 && next[top]==m) top-=m;
        }
}

int main()
{
        scanf("%s",a+1);    n=strlen(a+1);
        scanf("%s",b+1);    m=strlen(b+1);
        Stack[++top]=b[1];
        Deal(m,b,2);    Deal(n,a,1);

        for(int i=m+1;i<=top;i++)
            printf("%c",Stack[i]);

}