BZOJ3942 && 3940 Censoring

发表于 | 更新于

Link And This

Solution

每加入一个字符，用栈记录匹配到的位置。删除后缀就通过弹栈回到之前相应的位置实现

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+10;
namespace AC
{
	struct Node
	{
		Node *son[26],*fail,*last;
		int len;
		Node(){memset(son,0,sizeof(son));fail=last=0;len=0;}
		Node *&next(char c){return son[c-'a'];}
	}*root=new Node;
	Node *newNode()
	{
		static int SIZE=MAXN;
		static Node *ME=(Node*)malloc(SIZE*sizeof(Node)),*cur;
		cur=ME++;memset(cur->son,0,sizeof(cur->son));cur->last=cur->fail=0;
		cur->len=0;return cur;
	}
	void Insert(char *s)
	{
		Node *cur=root;
		int len=strlen(s+1);
		for(int i=1;i<=len;++i)
		{
			if(cur->next(s[i])) cur=cur->next(s[i]);
			else cur->next(s[i])=newNode(),cur=cur->next(s[i]);
		}
		assert(cur->len==0);
		cur->len=len;
	}
	void Build()
	{
		static Node *Q[MAXN];int he=1,ta=0;
		for(char c='a';c<='z';++c)
		{
			Node *&son=root->next(c);
			if(!son) son=root;
			else
			{
				son->fail=root;
				son->last=0;
				Q[++ta]=son;
			}
		}
		while(he<=ta)
		{
			Node *cur=Q[he++];
			for(char c='a';c<='z';++c)
			{
				Node *&son=cur->next(c);
				if(!son)
					son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->len?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
};
using namespace AC;
int main()
{
	//freopen("input","r",stdin);
	static char str[MAXN],S[MAXN],T[MAXN];
	static Node *f[MAXN];
	scanf("%s",S+1);int n;get(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",T+1);
		Insert(T);
	}
	Build();
	int len=0;f[0]=root;
	for(int i=1,L=strlen(S+1);i<=L;i++)
	{
		str[++len]=S[i];
		f[len]=f[len-1]->next(S[i]);
		if(f[len]->len) 
			len-=f[len]->len;//assert(cur->lens.size()==1);
		else if(f[len]->last) 
			len-=f[len]->last->len;//assert(cur->last->.size()==1);
	}
	str[len+1]=0;
	printf("%s\n",str+1);
	return 0;
}
/* AC Record(Bugs) *
 * WA 
 * * * * * * * * * */
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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e6+10;
int main()
{
	//freopen("input","r",stdin);
	static char S[MAXN],T[MAXN],dest[MAXN];
	static int p[MAXN],f[MAXN],len;
	scanf("%s%s",S+1,T+1);
	int s=strlen(S+1),t=strlen(T+1);
	p[1]=0;
	for(int i=2,j;i<=t;i++)
	{
		j=p[i-1];
		while(j && T[j+1]!=T[i]) j=p[j];
		if(T[j+1]==T[i]) j++;
		p[i]=j;
	}
	
	for(int i=1,j;i<=s;i++)
	{
		dest[++len]=S[i];
		j=f[len-1];
		while(j && T[j+1]!=S[i]) j=p[j];
		if(T[j+1]==S[i]) j++;
		if(j==t) len-=t;
		else f[len]=j;
	}
	dest[len+1]=0;
	printf("%s\n",dest+1);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */