BZOJ 2434 ali的打字机

发表于 | 更新于

Link

Solution

Fail树。子树和。经典思路。

Tips

AC自动机好像用到了不少记录某个字符匹配到哪个状态的情况啊。一开始太naive，直接暴力插入暴力查询，时间爆炸了。

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
//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
{
	const int SIGMA=26;
	const int SIZE=MAXN<<3;
	struct Node
	{
		Node *son[SIGMA],*fail,*last;int cnt;
		Node *&next(char c){return son[c-'a'];}
		int num();
	}*ME=(Node*)malloc(SIZE*sizeof(Node)),*HEAD=ME;
	int Node::num(){return this-HEAD+1;}
	Node *newNode()
	{
		static Node *cur;
		cur=ME++;cur->fail=cur->last=0;cur->cnt=0;
		memset(cur->son,0,sizeof(cur->son));return cur;
	}
	struct AC
	{
		Node *root;
		AC(){root=newNode();}
		void Build()
		{
			static Node *Q[SIZE];static int he,ta;
			he=1,ta=0;root->last=0;root->cnt=0;root->fail=root;
			for(char c='a';c<='z';++c)
				if(!root->next(c)) root->next(c)=root;
				else
				{
					root->next(c)->fail=root;
					root->next(c)->last=0;
					Q[++ta]=root->next(c);
				}
			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->cnt?son->fail:son->fail->last;
						Q[++ta]=son;
					}
				}
			}
		}
	}mata;
}
using namespace AC;
struct Edge{int to,pre;}e[MAXN<<1];int ec,id[MAXN];
void Adde(int f,int t)
{
	e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;
	e[++ec].to=f;e[ec].pre=id[t];id[t]=ec;
}
void BuildTree()
{
	for(Node *ptr=HEAD;ptr!=ME;++ptr)
		Adde(ptr->num(),ptr->fail->num());
}
int dfs[SIZE],dc,li[SIZE],ro[SIZE];
void DFS(int pos)
{
	dfs[li[pos]=++dc]=pos;
	for(int i=id[pos];i;i=e[i].pre)
	{
		int u=e[i].to;
		if(li[u]) continue;
		DFS(u);
	}
	ro[pos]=dc;
}
struct Bit
{
	int n,a[SIZE];
	#define lowbit(x) (x & -x)
	int Sum(int pos)
	{
		int res=0;
		for(;pos;pos-=lowbit(pos)) 
			res+=a[pos];
		return res;
	}
	void Add(int pos,int v)
	{
		if(!pos) return;
		for(;pos<=n;pos+=lowbit(pos)) 
			a[pos]+=v;
	}
	int Sum(int l,int r){return Sum(r)-Sum(l-1);}
	#undef lowbit
}bit;
struct List{int to,id,pre;}q[MAXN];int qc,head[MAXN],ANS[MAXN];
void Addq(int f,int t,int id){q[++qc].to=t;q[qc].id=id;q[qc].pre=head[f];head[f]=qc;}
int main()
{
	freopen("input","r",stdin);
	static char str[MAXN],*cptr=str,now[MAXN],*nptr=now;
	static Node *ref[MAXN],*state[MAXN];int sc=0;
	scanf("%s",str);
	state[0]=mata.root;
	for(cptr=str;*cptr;++cptr)
	{
		Node *cur=state[nptr-now];
		if(*cptr=='B')	*nptr--=0;//--nptr;
		else if(*cptr=='P') ref[++sc]=cur;
		else
		{
			*++nptr=*cptr;
			if(!cur->next(*nptr)) cur->next(*nptr)=newNode();
			cur=cur->next(*nptr);
			state[nptr-now]=cur;
		}
	}
	mata.Build();
	BuildTree();
	int root=mata.root->num();
	DFS(root);bit.n=dc;
	int m;get(m);
	for(int i=1;i<=m;i++)
	{
		int x,y;get(x),get(y);
		Addq(y,x,i);
	}
	while(nptr!=now) *nptr--=0;
	for(sc=0,cptr=str;*cptr;++cptr)
	{
		Node *cur=state[nptr-now];
		if(*cptr=='B')
		{
			*nptr--=0;
			bit.Add(li[cur->num()],-1);
		}
		else if(*cptr=='P')
		{
			++sc;
			for(int i=head[sc];i;i=q[i].pre)
			{
				int u=ref[q[i].to]->num();
				ANS[q[i].id]=bit.Sum(li[u],ro[u]);
			}
		}
		else
		{
			*++nptr=*cptr;
			state[nptr-now]=cur=cur->next(*nptr);
			bit.Add(li[cur->num()],1);
		}
	}	
	for(int i=1;i<=m;i++) printf("%d\n",ANS[i]);
	return 0;
}
/* AC Record(Bugs) *
 * WA sizeof array too small (turned out to be no problem)
 * WA printf %s error ---> printfing char*,deleted words must be cleared
 * MLE using list to contain,maybe n^2
 * WA in the for-loop below nptr wasn't reset
 *	  AND the characters in now[]wasn't cleared same as above
 * TLE Forever loop-->not forever
 *		the Inserting is too slow..too simple..
 *		the Matching is too slow..too simple..
 * * * * * * * * * */