题意:懒得写背景了，给你一个字符串init，要求你支持两个操作

(1):在当前字符串的后面插入一个字符串

(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)

你必须在线支持这些操作。

题解:可以想到用sam很好维护某个字符串在当前字符串中出现了几次,插入也直接add就好了,但是我们不能每次查询的时候topo然后更新sz,可以想到是不是可以每次加入一个新字符时,不断的向fa上跳,直到跳到根为止,但是这样最坏也是O(n)的,我们考虑怎么快速维护sam的fa树加边删边,更新链权值,很明显就能想到lct,lct打lazy标记更新链即可,sam中更新fa的时候在lct上加删边就好了,查询就splay到当前splay树的根,然后求val

注意:新建nq时,要把q的sz赋值给sz[nq]

/**************************************************************

    Problem: 2555

    User: walfy

    Language: C++

    Result: Accepted

    Time:20820 ms

    Memory:177688 kb

****************************************************************/

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize(4)

//#pragma GCC optimize("unroll-loops")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>

#define fi first

#define se second

#define db double

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

//#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define fin freopen("a.txt","r",stdin)

#define fout freopen("a.txt","w",stdout)

#define fio ios::sync_with_stdio(false);cin.tie(0)

template<typename T>

inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>

inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const double eps=1e-8;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=600000+10,maxn=3000000+10,inf=0x3f3f3f3f;

char s[maxn];

struct LCT{

    int fa[N<<1],ch[N<<1][2],rev[N<<1],sz[N<<1],q[N<<1],val[N<<1],add[N<<1];

    inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}

    inline void pushup(int x)

    {

        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;

    }

    inline void pushdown(int x)

    {

        if(rev[x])

        {

            rev[x]=0;swap(ch[x][0],ch[x][1]);

            rev[ch[x][0]]^=1,rev[ch[x][1]]^=1;

        }

        if(add[x])

        {

            if(ch[x][0])val[ch[x][0]]+=add[x],add[ch[x][0]]+=add[x];

            if(ch[x][1])val[ch[x][1]]+=add[x],add[ch[x][1]]+=add[x];

            add[x]=0;

        }

    }

    inline void Rotate(int x)

    {

        int y=fa[x],z=fa[y],l,r;

        if(ch[y][0]==x)l=0,r=l^1;

        else l=1,r=l^1;

        if(!isroot(y))

        {

            if(ch[z][0]==y)ch[z][0]=x;

            else ch[z][1]=x;

        }

        fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;

        ch[y][l]=ch[x][r];ch[x][r]=y;

        pushup(y);

    }

    inline void splay(int x)

    {

        int top=1;q[top]=x;

        for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];

        for(int i=top;i;i--)pushdown(q[i]);

        while(!isroot(x))

        {

            int y=fa[x],z=fa[y];

            if(!isroot(y))

            {

                if((ch[y][0]==x)^(ch[z][0]==y))Rotate(x);

                else Rotate(y);

            }

            Rotate(x);

        }

        pushup(x);

    }

    inline void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pushup(x);}

    inline void makeroot(int x){access(x),splay(x),rev[x]^=1;}

    inline int findroot(int x){access(x),splay(x);while(ch[x][0])x=ch[x][0];return x;}

    inline void split(int x,int y){makeroot(x),access(y),splay(y);}

    inline void cut(int x,int y){split(x,y);if(ch[y][0]==x)ch[y][0]=0,fa[x]=0;}

    inline void link(int x,int y){makeroot(x),fa[x]=y,splay(x);}

}lct;

struct SAM{

    int last,cnt;

    int ch[N<<1][26],fa[N<<1],l[N<<1],sz[N<<1];

    void ins(int c){

        int p=last,np=++cnt;last=np;l[np]=l[p]+1;

        for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;

        if(!p)fa[np]=1,lct.link(np,1);

        else

        {

            int q=ch[p][c];

            if(l[p]+1==l[q])fa[np]=q,lct.link(np,q);

            else

            {

                int nq=++cnt;l[nq]=l[p]+1;

                memcpy(ch[nq],ch[q],sizeof(ch[q]));

                lct.link(nq,fa[q]);lct.link(np,nq);

                lct.cut(q,fa[q]);lct.link(q,nq);

                fa[nq]=fa[q];fa[q]=fa[np]=nq;

                lct.splay(nq);lct.splay(q);

                lct.val[nq]=lct.val[q];

                for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;

            }

        }

        lct.split(np,1);

        lct.add[1]++,lct.val[1]++;

//        sz[np]=1;

//        for(;np;np=fa[np])sz[np]++;

    }

    void build(){

        int len=strlen(s);

        last=cnt=1;

        for(int i=0;i<len;i++)ins(s[i]-'A');

    }

    int cal()

    {

        int len=strlen(s);

        int now=1;

        for(int i=0;i<len;i++)

        {

            if(ch[now][s[i]-'A'])now=ch[now][s[i]-'A'];

            else return 0;

        }

        lct.splay(now);

        return lct.val[now];

    }

}sam;

void change(int mask)

{

    int len=strlen(s);

    for(int i=0; i<len; i++)

    {

        mask=(mask*131+i)%len;

        swap(s[mask],s[i]);

    }

}

int main()

{

    int n;scanf("%d%s",&n,s);

    sam.build();

    int mask=0;

    while(n--)

    {

        char op[10];

        scanf("%s%s",op,s);

        change(mask);

        if(op[0]=='A')

        {

            int len=strlen(s);

            for(int i=0;i<len;i++)sam.ins(s[i]-'A');

        }

        else

        {

            int ans=sam.cal();

            mask^=ans;

            printf("%d\n",ans);

        }

    }

    return 0;

}

/********************

23

ABAAB

Q AA

Q A

A ABA

Q AB

Q B

Q A

A AAA

Q AA

Q A

Q AAA

********************/