字符串算法

挖新坑！

字符串

字符串上的算法是抽象数据结构的极致，以SAM、PAM为代表的脑子进水高超数据结构深得出题人心。按照CF上AC人数排序翻译记录

126B[KMP]

题意：找到一个前缀，它既是后缀，也在中间出现过

考虑KMP的性质：$S[0..nxt[n]]$是$S_n$的后缀，那么$S[0..nxt[nxt[n]]]$也是$S_n$的后缀。看中间有没有出现某个前缀只需要看$nxt[i]$和前缀长度的大小关系

514C[hash]

题意：询问一个串能否通过修改一个字符变为给定集合中的串，$|\sum|=3$
枚举改什么，蛤希

471D[KMP]

题意：见原题图
差分后KMP，比T1还要裸。

535D[KMP]

题意：已知长为$n$的串匹配$S$有给定的$m$个起点，求原串方案数

432D[KMP]

题意：求前缀等于后缀的各长度的子串数量
同126B

633C[AC自动机]

题意：给出一篇小写字母、翻转单词、去掉空格的文章和词典，求原串
AC自动机上ALB，每次到一个$danger$点就DP一下

631D[KMP]

题意：给你两个个压缩后的字符串，求匹配起点数
去掉模式串首尾后kmp，放到另一串中判断

128B[SAM]

题意：第$k$大子串
先建一个sam，然后在上面DP就好了。
还看到有很多小哥把每个后缀放入堆中依次取出的做法，感觉强无敌。

526D[KMP]

题意：输出每个前缀是否能被表示为ABABABA的形状
在nxt上螺杆就好了吧

427D[]

题意：最长公共子串

149E[KMP]

题意：给定一个字符串$T$，接下来有$n$个字符串，对于每个字符串$S$,判断是否存在$T[a…b]+T[c…d]=S$
正反两遍kmp，记录一下匹配最远的位置

557E[]

题意：找出$s$的子串中字典序第$k$小的“半回文串”，给出半回文串定义是：对于任意$i\leq\frac{|s|}{2}$ 有$s[i] = s[len-i+1]$

441D[]

题意：输出字典序最小的两两元素交换方案，使交换后的排列最少交换$m$次可以变成$p_i = i$

533F[]

题目太长不敢翻译
题意：

235C[]

题意：给原串，和若干个询问串。求原串里有多少个不同子串可以通过询问串循环移动得到。

756D[]

太长不敢翻译
题意：

19C[]

没看懂

504E[hash]

题意：树链上子串求LCP
树剖后二分+hash

领悟了后缀数组后突然发现所有匹配问题都变成了数数题...

来源未知：Koishi Loves String

题意：支持在$S$前后加字符，$T$前后加字符，询问$T$在$S$内的匹配数，允许离线
第一眼感觉是不可做题。
qlj提醒我一下可以对整个串建个sam...
然后我怎么就轻易地发现是一道SB题...？

先把模型对应到整个串上：一个字符串，问$[c,d]$在$[a,b]$中的匹配数
先把模型对应到后缀树上：子串$[c,d]$一定是后缀树上的一条链，那么就便成求子树内有多少后缀对应的点在$[a,b]$中。
因为后缀树一定是静态的，所以题目也一定可以变成序列上询问区间$[l,r]$中有多少点值在$[a,b]$中，这个大家都会差分离线+BIT。
再把模型对应到后缀树组上：子串$[c,d]$包含的子树就变成了sa上的一段连续区间使得这些后缀和后缀$S_c$的$LCP$不小于$d-c+1$，按照height排序后并查集完全可以胜任。
既然能找到区间$[l,r]$，到这里，问题就十分simple了。
复杂度$O(n)+O(n\alpha(n))+O(n\log(n))$

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define N 1000010
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
//SAM
int n,O,p,q,np,nq,i,j,k,t,P,S[N],R[N],C[N][27],c[N][27],F[N],L[N],T[N],h[N];char s[N],r[N];bool v[N];
void A(int w)
{
    for(p=np,L[np=++O]=L[p]+1,T[np]=i;p&&!c[p][w];p=F[p])c[p][w]=np;
    if(!p)F[np]=1;else if(L[q=c[p][w]]==L[p]+1)F[np]=q;else for(L[nq=++O]=L[p]+1,memcpy(c[nq],c[q],sizeof(c[q])),F[nq]=F[q],F[q]=F[np]=nq;p&&c[p][w]==q;p=F[p])c[p][w]=nq;
}
void dfs(int x)
{
    if(T[x])S[++t]=T[x];
    for(int i=0;i<=26;i++)if(C[x][i])dfs(C[x][i]);
}
bool cmph(int x,int y){return h[x]>h[y];}
//BIT
int cc[N];
void add(int x){for(x++;x<N;x+=x&-x)cc[x]++;}
int ask(int x){if(x<0)return 0;int ret=0;for(x++;x;x-=x&-x)ret+=cc[x];return ret;}
//dsu
int f[N],ff[N],ll[N];
int fd(int x){return x==f[x]?x:f[x]=fd(f[x]);}
//Offline 1
int as;
struct Ask{int a,b,c,d,i;}E[N];
bool cmpA(Ask x,Ask y){return x.d>y.d;}
//Offline 2
int ans[N],tot;
struct poi{int a,b,c,i,_;}Q[2*N];
bool cmpQ(poi x,poi y){return x.a<y.a;}
//Inition
char Sf[N],Sb[N],Tf[N],Tb[N];
int sf,sb,tf,tb;
void work()
{
    //build SAM
    n=strlen(s+1);
    O=p=q=np=nq=k=t=P=0;
    clr(S),clr(R),clr(C),clr(c),clr(F),clr(L),clr(T),clr(h),clr(v);
    for(np=++O,i=n;i;i--)A(s[i]-'a');
    for(v[1]=i=1;i<=O;i++)if(T[i])
        for(P=n,j=i;!v[j];v[j]=1,j=F[j],P--)
            P-=L[j]-L[F[j]]-1,C[F[j]][s[P]-'a']=j;
    //build SA&Height
    for(dfs(1),i=1;i<=n;i++)R[S[i]]=i;
    for(i=1;i<=n;h[R[i++]]=k)
        for(k?k--:0,j=S[R[i]-1];s[i+k]==s[j+k];k++);
    //find (l,r] offline with dsu
    for(int i=1;i<=n;i++)ll[i]=f[i]=i,ff[i]=i+1;
    sort(ff+1,ff+n,cmph);
    for(int i=1,j=1,u,p,q;j<=as;j++)
    {
        for(;h[ff[i]]>E[j].d&&i<n;i++)
            p=fd(ff[i]-1),q=fd(ff[i]),f[p]=q,ll[q]=ll[p];
        //insert queries for BIT
        u=fd(R[E[j].c]);
        Q[tot++]=(poi){u,E[j].a,E[j].b-E[j].d,E[j].i,1};
        Q[tot++]=(poi){ll[u]-1,E[j].a,E[j].b-E[j].d,E[j].i,-1};
    }
    sort(Q,Q+tot,cmpQ);
    //find the answer offline with BIT
    for(int i=0,j=1;i<tot;i++)
    {
        for(;j<=Q[i].a&&j<=n;j++)add(S[j]);
        ans[Q[i].i]+=Q[i]._*(ask(Q[i].c)-ask(Q[i].b));
    }
}
int main()
{
    //Read-in&construct the string
    int _=read();
    for(int i=1;i<=_;i++)
    {
        int opt=read();
        if(opt==5)as++,E[as]=(Ask){sf,sb,tf,tb,as};
        else
        {
            char G;
            while('a'>c||'z'<c)G;
            if(opt==1)Sf[sf++]=c;
            if(opt==2)Sb[sb++]=c;
            if(opt==3)Tf[tf++]=c;
            if(opt==4)Tb[tb++]=c;
        }
    }
    for(int i=1;i<=sf;i++)s[++n]+=Sf[sf-i];
    for(int i=0;i<sb;i++)s[++n]+=Sb[i];
    s[++n]='{';
    for(int i=1;i<=tf;i++)s[++n]+=Tf[tf-i];
    for(int i=0;i<tb;i++)s[++n]+=Tb[i];
    //Handle queries
    for(int i=1;i<=as;i++)
        E[i].a=sf-E[i].a,E[i].b=sf+E[i].b,E[i].c=1+tf-E[i].c+sf+sb+1,E[i].d=tf+E[i].d+sf+sb+1-E[i].c;
    sort(E+1,E+1+as,cmpA);
    work();
    for(int i=1;i<=as;i++)printf("%d\n",ans[i]);
    return 0;
}