CF710F String Set Queries 做题记录

维护一个字符串集合，支持三种操作：

1. 加字符串
2. 删字符串
3. 查询集合中的所有字符串在给出的模板串中出现的次数

操作数 $m \leq 3 \times 10^5$，输入字符串总长度 $\sum |s_i| \leq 3\times 10^5$。

本题强制在线，应该在每次输出后调用fflush(stdout)。你只有在输出上一个询问的答案后才能读入下一组询问。

为了叙述方便，设 $len=\sum|s_i|$。

首先容易想到字符串哈希，开桶存某个哈希值有多少个，然后暴力枚举子串判断。这样时间复杂度是 $O(len^2)$ 的。

考虑优化，一个显然的做法是记录下集合内的串的长度，只枚举长度合法的字串。由于 $1+2+3+\dots+n=\frac{n(n+1)}2$，所以不同的长度最多只会有 $\sqrt len$ 个，时间复杂度为 $len\sqrt{len}$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>

using namespace std;

const int S=300005,bse=31,p1=998244353,p2=1000000007;

int n;
char a[S];
int p1p[S],p2p[S];
int cntlen[S];
set<int> lens;
map<pair<int,int>,int> cnt;
int pre1[S],pre2[S];

int main()
{
	p1p[0]=p2p[0]=1;
	for(int i=1;i<=S-3;i++) p1p[i]=1ll*p1p[i-1]*bse%p1,p2p[i]=1ll*p2p[i-1]*bse%p2;
	scanf("%d",&n);
	while(n-->0)
	{
		int tpe;
		scanf("%d%s",&tpe,a+1);
		if(tpe==1)
		{
			int x=0,y=0;
			int len=strlen(a+1);
			cntlen[len]++;
			if(cntlen[len]==1) lens.insert(len);
			for(int i=1;i<=len;i++)
			{
				x=(1ll*x*bse%p1+a[i]-'a'+1)%p1;
				y=(1ll*y*bse%p2+a[i]-'a'+1)%p2;
			}
//			printf("+ %d %d\n",x,y);
			cnt[make_pair(x,y)]++;
		}
		if(tpe==2)
		{
			int x=0,y=0;
			int len=strlen(a+1);
			cntlen[len]--;
			if(cntlen[len]==0) lens.erase(len);
			for(int i=1;i<=len;i++)
			{
				x=(1ll*x*bse%p1+a[i]-'a'+1)%p1;
				y=(1ll*y*bse%p2+a[i]-'a'+1)%p2;
			}
//			printf("- %d %d\n",x,y);
			cnt[make_pair(x,y)]--;
		}
		if(tpe==3)
		{
			long long ans=0;
			int m=strlen(a+1);
			for(int i=1;i<=m;i++)
			{
				pre1[i]=(1ll*pre1[i-1]*bse%p1+a[i]-'a'+1)%p1;
				pre2[i]=(1ll*pre2[i-1]*bse%p2+a[i]-'a'+1)%p2;
			}
			for(int len:lens)
			{
				for(int i=len;i<=m;i++)
				{
					int x=(pre1[i]-1ll*pre1[i-len]*p1p[len]%p1+p1)%p1;
					int y=(pre2[i]-1ll*pre2[i-len]*p2p[len]%p2+p2)%p2;
					ans+=cnt[make_pair(x,y)];
				}
			}
			printf("%lld\n",ans);
			fflush(stdout);
		}
	}
	return 0;
}