题意：
(1):在当前字符串的后面插入一个字符串
(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
字符串长度<=6e5，询问总长度<=3e6
分析：
考虑建个sam，然后把slink连起来就形成了一个前缀树
对于每个询问的串，就是求出它在sam里对应的点，然后在slink树种该点子树的size就是答案
用lct维护slink树即可
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
const int maxs=3e6; struct LCT
{
int ch[maxn+][],fa[maxn+],flip[maxn+];
int top;
int q[maxn+];
int sz[maxn+];
int tag[maxn+];
void init()
{ }
bool isroot(int x)
{
return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;
}
void add(int x,int data)
{
if(x)
{
tag[x]+=data;
sz[x]+=data;
}
}
void pushdown(int x)
{
int l=ch[x][],r=ch[x][];
if(flip[x])
{
flip[x]^=;flip[l]^=;flip[r]^=;
swap(ch[x][],ch[x][]);
}
if(tag[x])
{
add(l,tag[x]),add(r,tag[x]);
tag[x]=;
}
}
void rotate(int &x)
{
int y=fa[x],z=fa[y],l,r;
if(ch[y][]==x) l=;
else l=;
r=l^;
if(!isroot(y))
{
if(ch[z][]==y) ch[z][]=x;
else ch[z][]=x;
}
fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
ch[y][l]=ch[x][r];ch[x][r]=y;
}
void splay(int &x)
{
top=;
q[++top]=x;
for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
while(top) pushdown(q[top--]);
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))
{
if(ch[y][]==x^ch[z][]==y) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x)
{
for(int t=;x;t=x,x=fa[x])
splay(x),ch[x][]=t;
}
void link(int x,int f)
{
fa[x]=f;
access(f);
splay(f);
add(f,sz[x]);
}
void cut(int x)
{
access(x);
splay(x);
add(ch[x][],-sz[x]);
fa[ch[x][]]=,ch[x][]=;
}
int query(int x)
{
access(x);
splay(x);
return sz[x];
}
}lct; struct SAM
{
int maxlen[maxn+],minlen[maxn+],trans[maxn+][],slink[maxn+];
int sz,last;
void init()
{
for(int i=;i<;++i) trans[][i]=slink[]=-;
maxlen[]=minlen[]=;
sz=;
last=;
}
int build(int _maxlen,int _minlen,int* _trans,int _slink)
{
maxlen[++sz]=_maxlen;
minlen[sz]=_minlen;
for(int i=;i<;++i)
if(_trans==NULL) trans[sz][i]=-;else trans[sz][i]=_trans[i];
slink[sz]=_slink;
return sz;
}
int add(char ch,int u)
{
int c=ch-'A';
int z=build(maxlen[u]+,-,NULL,-);
lct.sz[z]=;
int v=u;
while(v!=-&&trans[v][c]==-)
{
trans[v][c]=z,v=slink[v];
}
if(v==-)//最简单的情况，suffix-path(u->S)上都没有对应字符ch的转移
{
minlen[z]=;
slink[z]=;
lct.link(z,);
return z;
}
int x=trans[v][c];
if(maxlen[v]+==maxlen[x])//较简单的情况，不用拆分x
{
minlen[z]=maxlen[x]+;
slink[z]=x;
lct.link(z,x);
return z;
}
int y=build(maxlen[v]+,-,trans[x],slink[x]); //最复杂的情况，拆分x，y表示<=maxlen[v]+1的那段
slink[y]=slink[x];
lct.link(y,slink[y]);
minlen[x]=maxlen[y]+;
lct.cut(x);
slink[x]=y;
lct.link(x,y);
minlen[z]=maxlen[y]+;
slink[z]=y;
lct.link(z,y);
int w=v;
while(w!=-&&trans[w][c]==x) trans[w][c]=y,w=slink[w];
minlen[y]=maxlen[slink[y]]+;
return z;
}
void append(char *s)
{
int len=strlen(s);
for(int i=;i<len;++i) last=add(s[i],last);
}
int query(char *s)
{
int len=strlen(s);
int now=;
for(int i=;i<len;++i)
{
now=trans[now][s[i]-'A'];
if(now==-) return ;
}
return lct.query(now);
}
}sam;
char s[maxs+];
int mask=;
void gets(int mask)
{
scanf("%s",s);
int len=strlen(s);
for (int j=;j<len;j++)
{
mask=(mask*+j)%len;
char t=s[j];
s[j]=s[mask];
s[mask]=t;
}
}
int main()
{
int q;
scanf("%d",&q);
sam.init();
scanf("%s",s);
sam.append(s);
while(q--)
{
scanf("%s",s);
if(s[]=='A')
{
gets(mask);
sam.append(s);
}
else
{
gets(mask);
int ans=sam.query(s);
mask^=ans;
printf("%d\n",ans);
}
}
return ;
}