根号重构AC自动机：HDU4787

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132812068

https://acm.hdu.edu.cn/showproblem.php?pid=4787

每次重构AC自动机复杂度非常大，但其实可以根号重构

维护两个AC自动机，一个大，一个小，然后对操作序列分块

小分块维护当前块的AC自动机，每次操作都重构

大分块维护之前的AC自动机，每 q\sqrt q 次操作重构

对于任意不支持修改数据结构，都可以根号重构

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 5000010
#define M 200010
//#define mo
int n, m, i, j, k, T, To;
int lstans; 
char str[N], st[N]; 
vector<char>s[M]; 
queue<int>q; 
map<int, int>mp; 

void slip() {
	int i, k, len; 
	len=strlen(str+1); k=lstans%len; ++k; 
	st[len+1]=0; 
	for(i=1; i<=len; ++i, k=(k+1)%len) {
		if(!k) k=len; st[i]=str[k]; 
	}
	for(i=1; i<=len; ++i) str[i]=st[i]; 
}

struct AC_auto_machine {
	int nxt[M][2], fail[M], p[M], tot; 
	vector<int>G[N]; 
	void clear() {
		for(int i=0; i<=tot; ++i) {
			fail[i]=nxt[i][0]=nxt[i][1]=p[i]=0; G[i].clear(); 
		}  
		tot=0; 
	}
	void Trie(int u, int i, int id) {
		if(!s[id][i]) return p[u]=1, void(); 
		int c=s[id][i]-'0';  
		if(!nxt[u][c]) nxt[u][c]=++tot; 
		Trie(nxt[u][c], i+1, id); 
	}
	void bfs() {
		int u, v, i; 
		q.push(1); 
		while(!q.empty()) {
			u=q.front(); q.pop(); 
			for(i=0; i<=1; ++i) {
				if(!nxt[u][i]) continue; 
				v=nxt[u][i]; k=fail[u]; 
				while(k && !nxt[k][i]) k=fail[k]; 
				if(nxt[k][i]) fail[v]=nxt[k][i]; 
				else fail[v]=1; 
				q.push(v); 
			}
		}
	}
	void dfs(int x) {
		for(int y : G[x]) p[y]+=p[x], dfs(y); 
	}
	void build(int l, int r) { //[l, r]建AC在a里面 
		int i, j, k; 
		clear(); 
		tot=1; 
		for(i=l; i<=r; ++i) if(s[i][0]!=-1) Trie(1, 0, i); 
		bfs(); 	
		for(i=2; i<=tot; ++i) G[fail[i]].pb(i); 
		dfs(1); 
	}
	int que() {
		int i, j=1, ans=0; 
		for(i=1; str[i]; ++i) {
			while(j && !nxt[j][str[i]-'0']) j=fail[j]; 
			if(nxt[j][str[i]-'0']) j=nxt[j][str[i]-'0']; 
			else j=1; 
			ans+=p[j]; 
		}
		return ans; 
	}
}AC1, AC2;

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	T=read();
	for(To=1; To<=T; ++To) {
		printf("Case #%lld:\n", To); 
		n=read(); m=sqrt(n); lstans=0; 
		AC1.clear(); AC2.clear(); mp.clear(); 
		for(i=1; i<=n; ++i) {
			scanf("%s", str); slip(); 
			if(str[0]=='+') {
				for(j=1, k=0; str[j]; ++j) k=(k*31+str[j])%998244353535353; 
				if(mp[k]) { s[i].pb(-1); continue; 
				} mp[k]=1; 
				for(j=1; str[j]; ++j) s[i].pb(str[j]); 	
				s[i].pb(0); 
			}
			else {
				lstans=AC1.que()+AC2.que(); s[i].pb(-1); 
				printf("%lld\n", lstans); 
			}
			if(i%m==0) AC1.build(1, i), AC2.clear(); 
			else AC2.build(i/m*m+1, i); 
		}
		for(i=1; i<=n; ++i) s[i].clear(); 
	}

	return 0;
}