Now Coach Pang is preparing for the Graduate Record Examinations as George did in 2011. At each day, Coach Pang can:
- "+\(w\)": learn a word \(w\)
- "?\(p\)": read a paragraph \(p\), and count the number of learnt words. Formally speaking, count the number of substrings of \(p\) which is a learnt words.
Given the records of N days, help Coach Pang to find the count. For convenience, the characters occured in the words and paragraphs are only '0' and '1'.
强制在线。
考虑暴力根号筹够，每 \(\sqrt{n}\) 个重建 AC 自动机。
开两个Ac自动机，一个拿来存最近根号个，每次插入重构。另一个每个根号个就插入重构。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=5e6+5;
typedef long long LL;
int q[N],l,r,m,t,n,ln[N];
LL ls;
char str[N],ss[M],st[M];
void shift(char ss[])
{
int m=strlen(ss);
for(int i=ls%m;i<m;i++)
st[i-ls%m]=ss[i];
for(int i=0;i<ls%m;i++)
st[m-ls%m+i]=ss[i];
for(int i=0;i<m;i++)
ss[i]=st[i];
}
struct ACAM{
int tr[N][2],ch[N][2],idx,c[N],fil[N],tg[N];
void insert(int l,int r)
{
int u=0;
for(int i=l;i<r;i++)
{
if(!ch[u][str[i]-'0'])
ch[u][str[i]-'0']=++idx;
u=ch[u][str[i]-'0'];
}
tg[u]=1;
}
int find(int l,int r)
{
int u=0;
for(int i=l;i<r;i++)
{
if(!ch[u][str[i]-'0'])
return 0;
u=ch[u][str[i]-'0'];
}
return tg[u];
}
LL ask()
{
int u=0;
LL ans=0;
for(int i=0;ss[i];i++)
u=tr[u][ss[i]-'0'],ans+=c[u];
return ans;
}
void clr()
{
for(int i=0;i<=idx;i++)
ch[i][0]=ch[i][1]=fil[i]=tg[i]=c[i]=tr[i][0]=tr[i][1]=0;
idx=0;
}
void build()
{
memset(c,0,sizeof(c));
l=1,r=0;
for(int i=0;i<2;i++)
if(tr[0][i]=ch[0][i])
q[++r]=ch[0][i];
while(l<=r)
{
for(int i=0;i<2;i++)
{
if(ch[q[l]][i])
fil[q[++r]=tr[q[l]][i]=ch[q[l]][i]]=tr[fil[q[l]]][i];
else
tr[q[l]][i]=tr[fil[q[l]]][i];
}
++l;
}
for(int i=0;i<=idx;i++)
c[i]=tg[i];
for(int i=0;i<=idx;i++)
c[q[i]]+=c[fil[q[i]]];
}
}x,y;
int main()
{
scanf("%d",&t);
for(int T=1;T<=t;T++)
{
printf("Case #%d:\n",T);
x.clr(),y.clr();
scanf("%d",&n),m=ls=0;
const int B=2;
for(int i=1;i<=n;i++)
{
char op=getchar();
while(op^'+'&&op^'?')
op=getchar();
if(op=='+')
{
++m;
scanf("%s",str+ln[m-1]);
shift(str+ln[m-1]);
ln[m]=ln[m-1]+strlen(str+ln[m-1]);
if(m%B==0)
{
for(int i=m-B+1;i<=m;i++)
{
x.insert(ln[i-1],ln[i]);
x.build();
}
y.clr();
}
else
{
if(!x.find(ln[m-1],ln[m]))
{
y.insert(ln[m-1],ln[m]);
y.build();
}
}
}
else
{
scanf("%s",ss);
shift(ss);
printf("%lld\n",ls=x.ask()+y.ask());
}
}
}
}