维护一个字符串集合,支持三种操作:
- 加字符串
- 删字符串
- 查询集合中的所有字符串在给出的模板串中出现的次数
操作数 ,输入字符串总长度 。
本题强制在线,应该在每次输出后调用
fflush(stdout)
。你只有在输出上一个询问的答案后才能读入下一组询问。
为了叙述方便,设 。
首先容易想到字符串哈希,开桶存某个哈希值有多少个,然后暴力枚举子串判断。这样时间复杂度是 的。
考虑优化,一个显然的做法是记录下集合内的串的长度,只枚举长度合法的字串。由于 ,所以不同的长度最多只会有 个,时间复杂度为 。
代码如下:
#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;
}