在这里放一些浅显易懂的证明吧。

kmp证明:

$next[i]$表示“以i结尾的非前缀子串“与”前缀子串”能够匹配的最长长度,即:

$next[i]=max\begin{Bmatrix}j\end{Bmatrix},j<i,A[1\sim j]=A[i-j+1\sim i]$

称每一个满足以上两个条件的$j$为$next[i]$的候选项。

引理:

若$j_0$为$next[i]$的一个候选项,即$j_0<i,A[1\sim j_0]=A[i-j_0+1\sim i]$,那么小于$j_0$的最大的$next[i]$的候选项是$next[j_0]$。换言之,$next[j_0]+1\sim j_0-1$之间都不是$next[i]$的候选项。

证明:

假设存在$next[j_0]<j_1<j_0$使得$j_1$为$next[i]$的候选项,即$A[1\sim j_1]=A[i-j_1+1\sim i]$,由于$A[1\sim j_0]=A[i-j_0+1\sim i]$,取后$j_1$个字符,即:$A[j_0-j_1+1\sim j_0]=A[i-j_1+1\sim i]=A[1\sim j_1]$,与$next[j_0]$“最大性"($next[j_0]$应为$j_1$)不符,故假设不成立。

另一方面,可以说明$next[j_0]$为$next[i]$的候选项。

$A[1\sim next[j_0]]=A[j_0-next[j_0]+1\sim j_0]$

$A[1\sim j_0]=A[i-j_0+1\sim i]$取后$next[j_0]$位,

即$A[j_0-next[j_0]+1\sim j_0]=A[i-next[j_0]+1\sim i]$

因此可以得知,$next[j_0]$为$next[i]$的候选项。

当正要计算$next[i]$的时候,$next[i-1]$已经统计完了。

根据引理,可知$next[i-1]$的所有候选项都可以从$next$数组中得到

根据定义,从大到小即为:$next[next[i-1]],next[next[next[i-1]]]\cdots \cdots$,若$j$要满足是$next[i]$的候选项,那么首先要满足$j-1$是$next[i-1]$的候选项,因此我们只要从$next[i-1]$的候选项中找出适配的最大值,再加上$1$,即为$next[i]$;

贴个代码吧

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=1e6+10;
int nxt[N],n,m;//next居然是系统函数 
char a[N],b[N];
void kmp()
{
    nxt[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&a[i]!=a[j+1])j=nxt[j];//j++
        if(a[i]==a[j+1])++j;nxt[i]=j;
    }
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&b[i]!=a[j+1])j=nxt[j];
        if(a[j+1]==b[i])++j;
        if(j==n){printf("%d %d\n",i-n+1,i);return ;}
    }
    puts("NO");
}
int main()
{
    scanf("%s%s",b+1,a+1);
    n=strlen(a+1),m=strlen(b+1);
    kmp();
    return 0;
}

kmp练习题

扩展KMP?(KMP+暴力)

真的莫得心思学这种愣头青算法。

回顾一下$\operatorname{kmp}$的$next$数组,即为$A[1\sim next[i]]=A[i-next[i]+1\sim i]$

首先人为定义一下:$n=strlen(A+1),m=strlen(B+1)$

可是$\operatorname{EXKMP}$贼优秀,是$A[1\sim next[i]]=A[i\sim i+next[i]-1]$且保证$next[i]$最大

同样是自己弄自己,你咋那么优秀呢?

为了方便起见,$next[1]=n$,直接重合。

接着我们要暴力弄一下$next[2]$,如下图

在这里插入图片描述
就像这样,$next[2]=6$,即$A[1\sim 6]=A[2\sim 7]$,至于有什么用,等会就知道了。

这时候,再定义$k$,这个$k$表示的就是在当前搜索过的范围以内(因为这是线性算法,所以是从$1$到$i$)能到达最远(也就是说$k+next[k]-1$最大)的编号。

定义一个$ed$,让它等于$k+next[k]-1$,那么由$nex$t这个数组的定义我们就可以得到一个等式:$A[1\sim next[k]]=A[k\sim ed]$,由于$ed=k+next[k]-1$,则$next[k]=ed-k+1$,故有$A[1\sim ed-k+1]=A[k\sim ed]$,代换来,代换去,还是那条柿子,如下图。

在这里插入图片描述

假设现在已经扫到第$i$个位置了,且$ed>i$,则如下图:
在这里插入图片描述
那么,不是就有状态可以继承了吗?,即:$A[i\sim ed]$=A[$i-k+1\sim ed-k+1]$。

现在有$L=next[i-k+1]$,那么$A[1\sim L]=A[i-k+1\sim i-k+L]$

但是如果这样,不是有可能出现两种情况吗?

比如:
在这里插入图片描述

还有

在这里插入图片描述
所以要分类讨论,

当$ed-k+1>i-k+L$,即
在这里插入图片描述

根据$L=next[i-k+1]$的定义,即$A[1\sim L]=A[i-k+1\sim i-k+L]$,且L已经最大,

换种说法,也就是$A[L+1]$不等于$A[i-k+L+1]$。

又因为$A[i\sim ed]$=A[$i-k+1\sim ed-k+1]$,

可以说明$A[i-k+1\sim i-k+L]=A[i\sim i+L-1]=A[1\sim L]$,且$A[i+L]$不等于$A[L+1]$。因此$next[i]=L$即可。

另一种情况,即:
在这里插入图片描述
根据$next[k]$的定义,可以直接得到$A[ed+1]$不等于$A[ed-k+2]$,令$next[i]=ed-i+1$即可.

注意,有可能$ed<i$

貌似?

还有等于的情况?

在这里插入图片描述

这是我们只能确定$A[1\sim next[i]]$与$A[i\sim i+next[i]-1]$中有$ed-i+1$长的公共前缀长度,
但是无法确定究竟有多长,那只好暴力了(滑稽)。

$extend[i]$的意义在于是求$B[i,i+n-1]$与$A$的最长公共前缀长度

求$extend$数组类似,只需要记住一点,$ed=k+extend[k]-1,L=nxt[i-k+1]$,这是由于$nxt[i]$可能不存在,但由于$extend$是统计$A$串与$B$串的最长公共前缀长度,不可能大于$A$串的长度,则$nxt[i-k+1]$始终合法,对于当前$i$,求$extend$的方法,类似于求$nxt$的方法,也是分类讨论。如图,下面这段红色区间就是当前可以利用的区间,因为$b[k,k+extend[k]-1]$与$b[i,i+n]$重合了$b[i,k+extend[k]-1]$,类似这样。

在这里插入图片描述

接着分类讨论即可。

EXKMP练习题

Code

#include<cstdio>
#include<cstring>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e6+10;
char a[N],b[N];
int n,m,nxt[N],extend[N];
int main()
{
    scanf("%s%s",b+1,a+1);n=strlen(a+1),m=strlen(b+1);
    nxt[1]=n;int x=1,k;
    while(x+1<=n&&a[x]==a[x+1])++x;
    nxt[2]=x-1;k=2;
    for(int i=3;i<=n;i++)
    {
        int ed=k+nxt[k]-i,L=nxt[i-k+1];//int ed=k+nxt[k]-1;
        if(ed>L)nxt[i]=L;
        else
        {
            x=ed;
            if(x<0)x=0;
            while(x+i<=n&&a[x+1]==a[x+i])++x;//ed-i+1==L 
            nxt[i]=x;k=i;//i+nxt[i]-1>k+nxt[k]-1;
        }
    }
    x=1;
    while(x<=n&&a[x]==b[x])++x;
    extend[1]=x-1;k=1;
    for(int i=2;i<=m;i++)
    {
        int ed=k+extend[k]-i,L=nxt[i-k+1];//i-k+1<=n,A[1,nxt[i-k+1]
        if(ed>L)extend[i]=L;
        else
        {
            x=ed;
            if(x<0)x=0;
            while(x<n&&x+i<=m&&a[x+1]==b[x+i])++x;
            extend[i]=x;k=i;
        }
    }
    for(int i=1;i<=m;i++)printf("%d ",extend[i]);puts("");
    return 0;
}

Manacher算法(马拉车算法)

马拉着车的算法果然不一样

马拉车用来解决回文串问题,简直跑得飞快($O(n)$),($O(n^2)$大法好!)

回文串就是类似"${\color{blue}baab}$","${\color{red}abggba}$"的字符串,也就是从左往右读,或者从右往左读,都是一样的字符串。

但是回文串处理起来,要分奇偶。

但是将"${\color{blue}baab}$",变成"$\#b\#a\#a\#b\#$"就可使回文串变成奇数。

运用这种方法,就可以避免奇偶的问题了。

那么如何实现快速找回文串呢?
(注:讲解中的$r-i$实际上是$r-i+1$,程序实现也是$r-i$,其实这个$r$可以代表为$r$这个位置与$l$不匹配,增减之后不影响结果。)

设现在够到最远的(也就是右端点最远)回文串的中心为$pos$,右端点为$r$,设$p$数组,记录回文长度,即:$p[i]$记录已i为中心的回文长度。

假设现在搜索到$i$,且$i< r$,如图,

在这里插入图片描述
若$p[j]>r-i$,如图,
在这里插入图片描述
根据回文串性质,$A[l+1 \sim j]=A[r-1\sim i]$,可是再往$l$,$r$扩展,就不行了(因为$A[l]$不等于$A[r]$),所以$p[i]$只能先等于$r-i$,继承状态之后再扩展。

否则,如图,

在这里插入图片描述

直接继承$p[j]$即可。

若$i\ge R$,没得谈,只得暴力扩展。

Code

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=1e5+10;
int p[N<<1];
char a[N],b[N<<1];
void Manacher()
{
    int len=strlen(a+1);
    for(int i=1;i<=len;i++)b[2*i-1]='#',b[2*i]=a[i];
    len=len*2+1;
    b[len]='#';
    int pos=0,r=0;
    for(int i=1;i<=len;i++)
    {
        int j=2*pos-i;
        if(i<r)p[i]=min(p[j],r-i);
        else p[i]=1;
        while(1<=i-p[i]&&i+p[i]<=len&&b[i-p[i]]==b[i+p[i]])++p[i];
        if(i+p[i]>r)
        {
            pos=i;
            r=i+p[i];
        }
    }
    int ans=0;
    for(int i=1;i<=len;i++)ans=max(ans,p[i]-1);
    printf("%d\n",ans);
}
int main()
{
    while(scanf("%s",a+1)!=EOF)Manacher();
    return 0;
}

AC自动机

让我们首先学习一下$\operatorname{Trie}$树,

来自百度,字典树又称单词查找树,$\operatorname{Trie}$树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

实现原理,类似继承前缀,减少空间复杂度,如图。

有字符串"${\color{blue}aab,ab,b}$"
在这里插入图片描述
所以,$\operatorname{Trie}$是一个十分简单的东西

$AC$自动机比$\operatorname{Trie}$树多出一个$fail$指针,指向同类型的其他节点,例如:一个字母$a_1$节点,$fail$指针指向且另外一个字母$a_2$,且另外一个字母$a_2$的父亲$f_2$,同样是$f_1$的$fail$指针的集合里(有可能不是$f_1$的$fail$所指向的那个。)

$t[x].fail$的深度小于$x$的深度,才能保证合法性(深度大不一定保证合法)
特别地,$t[0]$的所有儿子指向$t[0]$。

在这里插入图片描述
AC自动机练习题

code

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=5e5+10;
const int M=1e6+10;
struct node{int c[27],s,fail;}t[N];
int cnt,ans,n;char s[M];
void clean(int x){t[x].s=t[x].fail=0;memset(t[x].c,-1,sizeof(t[x].c));}
void build(int root)
{
    int x=root;int len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        int y=s[i]-'a'+1;
        if(t[x].c[y]==-1){t[x].c[y]=++cnt;clean(cnt);}
        x=t[x].c[y];
    }
    ++t[x].s;
}
int q[N];
void bfs()
{
    int l=1,r=2;
    while(l!=r)
    {
        int x=q[l++];
        for(int i=1;i<=26;i++)
        {
            if(t[x].c[i]==-1)continue;
            int y=t[x].c[i];
            if(!x)t[y].fail=0;//指向根节点
            else
            {
                int k=t[x].fail;
                while(k!=0&&t[k].c[i]==-1)k=t[k].fail;
                t[y].fail=(t[k].c[i]==-1?0:t[k].c[i]);
            }
            q[r++]=y;
        }
    }
}
void solve()
{
    int len=strlen(s+1);
    int x=0;int k;ans=0;
    for(int i=1;i<=len;i++)
    {
        int y=s[i]-'a'+1;
        while(x!=0&&t[x].c[y]==-1)x=t[x].fail;
        x=t[x].c[y];
        if(x==-1){x=0;continue;}
        k=x;
        while(k)
        {
            ans+=t[k].s;
            t[k].s=0;
            k=t[k].fail;
        }
    }
    printf("%d\n",ans);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);cnt=0;clean(0);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s+1);
            build(0);
        }
        bfs();scanf("%s",s+1);
        solve();
    }
    return 0;
}

后缀数组(怀疑人生系列)

思路挺好懂的。

前置知识

一点点的基数排序

一点点的字符串知识。

基数排序

大概学过桶排序吧,基数排序就是很多个桶,把数给分类一下,然后从小到大记录前缀和,再还原数就好了,桶够多$O(n)$。

后缀

举个栗子吧。

比如${\color{blue}abbaba}$

它的所有后缀就是

$abbaba$,$bbaba$,$baba$,$aba$,$ba$,$a$

系统地讲,就是从某个位置$i$到字符串结尾结束的一个特殊子串,即$A[i\sim n]$,记为$Suffix(i)$,以下简写为$sf(i)$。

通常来讲,字典序排序,要从$1\sim$串长比较每一位的字母的ASCII码的大小。
(详细见百度)

将以上栗子排序之后,从小到大表示为

$a,aba,abbaba,ba,baba,bbaba$

比如这道题

就是要求排序后的后缀第一个字母出现的位置。

好了,进入正题,

先弄两个数组出来,

一个后缀数组$SA$,保证 $sf(SA[i]) <sf(SA[i+1])$,$1≤i<n$。
也就是将 $A$ 的 $n$ 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺
次放入$SA$中(排名第几的是谁)

一个名次数组$Rank$,保存后缀$i$在从小到大排列的所有后缀的名次(你排第几)

这两个数组是互逆的。

举个栗子:${\color{red}aabaaab}$

引进一张罗穗骞dalao的图片

在这里插入图片描述

倍增算法(DA)

现设字符串长度为$n$。

倍增算法的主要思路是:用倍增的方法对每个字符开始的长度为 $2^k$ 的子字
符串进行排序,求出排名,即 $rank$ 值。

$k$ 从 $1$ 开始,每次加 $1$,当 $2^k$ 大于$n$以
后,每个字符开始的长度为 $2^k$ 的子字符串便相当于所有的后缀。并且这些子字
符串都一定已经比较出大小, 即 $rank$ 值中没有相同的值, 那么此时的 $rank$ 值就
是最后的结果。

每一次排序都利用上次长度为$2^{k-1}$的字符串的 $rank$ 值,那么长
度为$2^k$的字符串就可以用两个长度为$2^{k-1}$的字符串的排名作为关键字表示,然
后进行基数排序, 便得出了长度为$2^{k-1}$的字符串的 $rank$ 值。

如何找到$O(1)$后一个长度为$2^{k-1}$的字符串呢?

经过观察可以发现,后缀$i(i\le n-2^k+1)$的第$2^{k-1}+1\sim 2^k$的字符恰好为后缀$i+2^{k-1}$的前$2^{k-1}$个字符。

以字符串“$aabaaaab$”
为例, 整个过程如图所示。 其中$x,y$是表示长度为$2^{k-1}$的字符串的两个关键字

在这里插入图片描述
思路貌似就讲完了,实现的话$\cdots\cdots$

前方高能

void DA(char *r,int n,int m)
{
    int *x=wa,*y=wb,*t;
    for(int i=1;i<=n;i++)++c[x[i]=r[i]];
    for(int i=2;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
    for(int j=1,p=1;p<n;j<<=1,m=p)
    {
        p=0;
        for(int i=n-j+1;i<=n;i++)y[++p]=i;
        //n-j+1~n是没有第二关键字的,它们的第二关键字就是它们自己
        for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;
        for(int i=1;i<=n;i++)wv[i]=x[y[i]];
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)++c[wv[i]];
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[wv[i]]--]=y[i];
        t=x;x=y;y=t;p=1;x[sa[1]]=1;
         for(int i=2;i<=n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p:++p;
        Debug(x,sa,n);
    }
    for(int i=1;i<=n;i++)qw(sa[i]),putchar(' ');
}

$Tips$:

$y$数组其实是整一个第二关键字排序后的一个编号结果(没有第二关键字的排在前面,之后按第一个关键字也就是$sa$从小到大排下来的编号结果)

for(int i=n-j+1;i<=n;i++)y[++p]=i;
//n-j+1~n是没有第二关键字的,它们的第二关键字就是它们自己
for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;//排名要从小到大·

个人认为对于$i<j<k,x[y[i]]=x[y[j]]=x[y[k]]$,根据$y$数组的性质,排序后,$y[i]$的排名<$y[j]$的排名<$y[z]$的排名

证明如下,

由于$i<j<k$,设$y[i]=sa[w_1]-t,y[j]=sa[w_2]-t,y[k]=sa[w_3]-t$,

可知$w_1<w_2<w_3$,即可说明后缀$sa[w_1]-t$的第二关键字优于$sa[w_2]-t$,同理,证毕。

因此我们可以得出,$y$数组的下标反应第二关键字(的排名),对应下标的值反应后缀的编号。

之后用第二关键字$y$,对第一关键字进行排序,求出新的$sa$值。
(其实就是同一个堆中的元素,通过$y$数组出现的早晚,来判断谁排在前,谁排在后。)

for(int i=1;i<=n;i++)wv[i]=x[y[i]];
for(int i=1;i<=m;i++)c[i]=0;
for(int i=1;i<=n;i++)++c[wv[i]];
for(int i=2;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--)sa[c[wv[i]]--]=y[i];

code

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=1e6+10;
void qw(int x)
{
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
char s[N];
int wa[N],wb[N],wv[N],c[N],sa[N];
bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void DA(char *r,int n,int m)
{
    int *x=wa,*y=wb,*t;
    for(int i=1;i<=n;i++)++c[x[i]=r[i]];
    for(int i=2;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
    for(int j=1,p=1;p<n;j<<=1,m=p)
    {
        p=0;
        for(int i=n-j+1;i<=n;i++)y[++p]=i;
        for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;
        for(int i=1;i<=n;i++)wv[i]=x[y[i]];//第二关键字的sa[i]-j的第一关键字 
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)++c[wv[i]];
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[wv[i]]--]=y[i];
        t=x;x=y;y=t;p=1;x[sa[1]]=1;
         for(int i=2;i<=n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p:++p;
    }
    for(int i=1;i<=n;i++)qw(sa[i]),putchar(' ');
}
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1),m=122;
    DA(s,n,m);
    return 0;
}

后缀数组的补充

${\color{black}\text{height}}$数组

定义 $\text{height[i]=suffix(sa[i-1])}$和 $\text{suffix(sa[i])}$的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀。

那么对于 $j$ 和 $k$,不妨设$\text{rank[j]<rank[k]}$,则有以下性质:$\text{suffix(j)}$ 和 $\text{suffix(k)}$的最长公共前缀为$\text{height[rank[j]+1],height[rank[j]+2], height[rank[j]+3], … ,height[rank[k]]}$中的最小值(具有传递性,从小状态滚到大状态)。

设$rank[k]=rank[j]+2$,则$height[rank[j+1]]$表示为编号$j$的后缀与排名$rank[j+1]$的最长公共前缀,$height[rank[j+2]]$表示为编号为$j+1$的后缀与排名$rank[j+2]$的最长公共前缀,那么$min(height[rank[j+1]],height[rank[j+2]])$就可以作为编号为$j$的后缀与编号为$k$的最长公共前缀。

之后以此类推。

以下再引用罗穗骞dalao的图片

例如,字符串为“$\text{aabaaaab}$” ,求后缀“$\text{abaaaab}$” 和后缀“$\text{aaab}$” 的最长公
共前缀,如图所示
在这里插入图片描述
如何高效求$\text{height}$数组呢?

设$h[i]=height[rank[i]]$,也就是$suffix(i)$和在它前一名的后缀的最长公共前
缀。

则有$$h[i]\ge h[i-1]-1$$

证明:

$suffix(k)$是$suffix(i-1)$的前一个排名的后缀,即$sa[rank[i-1]-1]=k$,它们的最长公共前缀为$h[i-1]$,也就是$A[k\sim k+h[i-1]-1]=A[i-1\sim i+h[i-1]-2]$。

那么 $suffix(k+1)$将排在 $suffix(i)$的前面(这里要求 $h[i-1]>1$,如果$h[i-1]≤1$,原式显然成立) 并且 $suffix(k+1)$和 $suffix(i)$的最长公共前缀是$h[i-1]-1$,$A[k+1\sim k+h[i-1]-1]=A[i\sim i+h[i-1]-2]$。

根据上文性质,$suffix(i)$和在它前一名的后缀的最长公共前缀至少是 $h[i-1]-1$。按照 $h[2],h[3],……,h[n]$的顺序计算,并利用 h 数组的性质,时间复杂度可以降为 $O(n)$

后缀数组练习题

后缀自动机SAM

(这玩意真难学)

前置知识

没有。

由于篇幅很长,本人很懒,所以