String Set Queries[CF710F]

发表于 分类于

fflush(stdout) 搞了我好久。。。

题目链接

链接

题意

维护一个字符串集合，支持：

  • 插入一个字符串

  • 删除一个原有的字符串

  • 询问一个字符串，问字符串集合中的元素在该字符串中出现次数之和。

强制在线。

$\sum |S|\leq 3\times 10^5$

题解

这个trick真的太妙了…

首先删除是假的，因为满足可减性，把删掉的字符串形成的集合的贡献删掉就可以了。

这个东东显然可以用AC自动机/SAM维护。

但是不支持强制在线啊。。。

那么你就可以写一个广义SAM+LCT就好了

trick：对字符串进行二进制分组。

也就是说，我们维护 $\log |S|$ 个AC自动机，第 $i$ 个自动机中存 $2^i$ 个字符串。

每次插入时维护一个自动机。

枚举第 $i$ 个自动机，看是否为空，若为空，则插入，然后getfail。

否则将当前自动机和第 $i$ 个自动机合并。合并AC自动机跟合并Trie类似。

每个字符串都只会改变 $\log |S|$ 个位置。

因此时间复杂度 $O(|S|\log |S|)$。

程序

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=3000010;
const int S=26;
const int M=19;
struct AC_Auto{
	int ne[N][S],fail[N],cnt,val[N],rt[M]; bool bo[N];
	AC_Auto() {cnt=1;}
	inline void dfs(int x,int y)
	{
		bo[x]|=bo[y];
		fo(i,0,S-1)
		{
			if(!ne[y][i]) continue;
			else if(!ne[x][i]) ne[x][i]=ne[y][i];
			else dfs(ne[x][i],ne[y][i]); 
		}
	}
	queue<int> q;
	inline void getfail(int x)
	{
		for(;!q.empty();q.pop());
		q.push(x); fail[x]=val[x]=0;
		for(int u,p,v;!q.empty();)
		{
			u=q.front(); q.pop();
			for(int i=0;i<S;i++)
				if(v=ne[u][i])
				{
					q.push(v); p=fail[u];
					for(;p&&!ne[p][i];p=fail[p]);
					fail[v]=p?ne[p][i]:x;
					val[v]=val[fail[v]]+bo[v];
				}
		}
	}
	inline void ins(char *s)
	{
		int n=strlen(s+1),u=++cnt,p=u;
		fo(i,1,n)
		{
			ne[u][s[i]-'a']=++cnt;
			u=ne[u][s[i]-'a'];
		}
		bo[u]=1; u=p;
		fo(i,0,M-1)
			if(!rt[i]){rt[i]=u; getfail(rt[i]); break;}
			else {dfs(u,rt[i]); rt[i]=0;}
	}
	inline ll ask(char *s)
	{
		int n=strlen(s+1),c,u;
		ll ans=0;
		fo(j,0,M-1)
			if(rt[j])
			{
				u=rt[j];
				fo(i,1,n)
				{
					c=s[i]-'a';
					if(ne[u][c]) u=ne[u][c];
					else
					{
						for(;u&&!ne[u][c];u=fail[u]);
						u=u?ne[u][c]:rt[j];
					}
					ans+=val[u];
				}
			}
		return ans;
	}
}A,B;
char t[300010]; int opt;
int main()
{
	CASET
	{
		opt=read(); scanf("%s",t+1);
		if(opt==1) A.ins(t);
		else if(opt==2) B.ins(t);
		else printf("%lld\n",A.ask(t)-B.ask(t));
		fflush(stdout);
	}
	return 0;
}