CF710F String Set Queries 做题记录

维护一个字符串集合,支持三种操作:

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

操作数 m3×105m \leq 3 \times 10^5,输入字符串总长度 si3×105\sum |s_i| \leq 3\times 10^5

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

为了叙述方便,设 len=silen=\sum|s_i|

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

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