【总结】后缀数组

前言

据说后缀数组是个比较常用的玩意。。。不过我也没在什么大赛上遇到过。。。但防范于未然嘛。。。CQOI2018的Matrix-Tree定理*。。。不能再发生了

概述

后缀数组是一种高效字符串处理的工具，主要就是快速计算静态的LCP（动态可以考虑平衡树+字符串hash:详见BZOJ1014[JSOI2008]）

虽然看起来没什么卵用，但LCP用处可就大了。其应用相当广泛，具体的可以在后面的例题中体现。

算法介绍

后缀数组，顾名思义是将一个字符串的所有后缀按字典序排序后，得到的数组。

这里不得不推荐后缀数组论文。。。可以说是难得一见的清晰明了的集训队论文。。。

定义ranki$ran{k}_i$表示第i个后缀的排名
定义sai$s{a}_i$表示排名为i的后缀是哪个

很显然这两数组只要求其一，就能在O(n)$O(n)$复杂度内求出另一个。

为了便于理解，这里给出一个实例（摘自论文）

那么，如何快速地求这个数组呢？

这里就要用到倍增的思想了（DC3感觉不好写而且倍增也慢不到哪里去，所以这里就不写了）

很显然，如果我们求出所有后缀前k个字符所形成的排名时，就可以利用基数排序，在O(n)$O(n)$复杂度内求出所有后缀前2×k$2\times k$个字符所形成的排名。

这个图就很形象了。
可以看到，每次我们根据 所有后缀前k$k$个字符 的排名情况，可以得到一个二元组表示 所有后缀前2∗k$2\ast k$个字符 所形成的排名。这里再以第一个为优先，第二个为次优先，将所有二元组排名，就能得到一个新的排名，而这个排名就正是 所有后缀前2∗k$2\ast k$个字符 所形成的排名。

应该还是比较简单的？

这样一来，我们就可以在O(nlogn)$O(nlogn)$复杂度内求出rank数组了。

当然，有这个还不够，我们需要引入一个新的数组。

h$h$ 数组：定义 hi=suffix(sai−1)和suffix(sai)$h_i=suffix(s{a}_{i-1})和suffix(s{a}_i)$的最长公
共前缀，也就是排名相邻的两个后缀的最长公共前缀。

很显然，这样一来就有一个很有用的性质：
suffix(j) 和 suffix(k) 的 最 长 公 共 前 缀 为 hrankj+1,hrankj+2,hrankj+3,…,hrankk$h_{ran{k}_j+1},h_{ran{k}_j+2},h_{ran{k}_j+3},\dots ,h_{ran{k}_k}$中的最小值。其实这就是LCP了。

那么如何高效地求出h$h$数组呢？

这里又有一个性质了hi≥hi−1−1$h_i\ge h_{i-1}-1$这个其实证明起来也很简单。。。简单地说是因为这是后缀的排名。所以有这个后缀加上前一个字符所组成的新的后缀来维护下限。

所以，可以按顺序求h$h$数组，每次从hi−1−1$h_{i-1}-1$位置开始枚举，这样总的复杂度也是O(n)$O(n)$级的。

例题（摘自论文）

重复子串

1、可重叠最长重复子串

h数组求最大值

2、不可重叠最长重复子串

这个跟上面的比起来就略显复杂。
可以用二分答案解决

将h数组分成每个内部的值都不小于k的最大的块

然后，很显然每个块内部的后缀都是满足”最长重复子串不小于k”这个条件的。
要判断的无非就是每个块内部位置最小和最大的是否间隔不小于k罢了。

3、可重叠的 k 次最长重复子串

有了上一题的启发，这个就非常简单了，同样是二分答案。详细的可以自己思考一下。

子串的个数

计算不同子串个数

这个嘛。。可以反过来，计算总的子串个数，减去重复子串个数即可。重复子串个数可以通过算贡献的方式求得。按照sa数组依次求贡献。

回文子串

这个问题就很无聊了。。。。将原字符串倒过来，再将两个合在一块中间加个没出现过的特殊字符，以隔开两部分。最后求两部分所有位置最长公共前缀即可。

重复次数最多的连续重复子串

其实也是暴力枚举长度然后check，时间复杂度是调和级数
O(n1+n2+……+nn)=O(nlogn)$O(\frac{n}{1}+\frac{n}{2}+\dots \dots +\frac{n}{n})=O(nlogn)$

最长公共子串

其实和上面的回文子串有些类似，都是将两个字符串合并，中间加上一个字符。
只不过现在求的是两部分中某两个后缀的最长公共前缀的最大值。

论文后面的题目都没有什么新的方法了，基本上都是从上面的例题中进行改动而得到的算法。所以这里不再赘述。

附一个POJ1743的模板

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define SF scanf
#define PF printf
#define MAXN 500010
#define MAXSIZE 210
#define INF 0x3FFFFFFF
using namespace std;
int sa[MAXN],ws[MAXN],wv[MAXN],wa[MAXN],wb[MAXN],ra[MAXN],h[MAXN];
int n,r[MAXN],m=MAXSIZE,ans;
int tot[MAXN];
inline int cmp(int *v,int a,int b,int l){
    return v[a]==v[b]&&v[a+l]==v[b+l];
}
void da(){
    m=MAXSIZE;
    //memset(wa,0,sizeof wa);
    //memset(wb,0,sizeof wb);
    //memset(wv,0,sizeof wv);
    int *x=wa,*y=wb,p;
    for(int i=0;i<m;i++) ws[i]=0;
    for(int i=0;i<n;i++) ws[x[i]=r[i]]++;
    for(int i=1;i<m;i++) ws[i]+=ws[i-1];
    for(int i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
    for(int j=1;j<=n&&x[sa[n-1]]<n-1;j*=2,m=p){
        p=0;
        //PF("*");
        //PF(" 1");
        for(int i=n-j;i<n;i++)
            y[p++]=i;
        for(int i=0;i<n;i++)
            if(sa[i]>=j)
                y[p++]=sa[i]-j;
        //PF(" 2");
        for(int i=0;i<n;i++) wv[i]=x[y[i]];
        for(int i=0;i<m;i++) ws[i]=0;
        for(int i=0;i<n;i++) ws[wv[i]]++;
        //PF(" %d %d ",n,m);
        for(int i=1;i<m;i++) ws[i]+=ws[i-1];
        for(int i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
        //PF(" 4");
        p=1;
        int *t=x;
        x=y;
        y=t;
        x[sa[0]]=0;
        for(int i=1;i<n;i++){
            if(cmp(y,sa[i-1],sa[i],j))
                x[sa[i]]=p-1;
            else
                x[sa[i]]=p++;
        }
        //PF(" 5");
    }
}
void height(){
    int x=sa[ra[0]-1];
    h[ra[0]]=0;
    for(int i=0;i+x<n;i++){
        if(r[i]!=r[x+i])
            break;
        h[ra[0]]++;
    }
    for(int i=1;i<n-1;i++){
        h[ra[i]]=h[ra[i-1]]-1;
        if(h[ra[i]]<0)
            h[ra[i]]=0;
        x=sa[ra[i]-1];
        for(int j=h[ra[i]];j+x<n&&j+i<n;j++){
            if(r[i+j]!=r[x+j])
                break;
            h[ra[i]]++;
        }
    }
}
bool check(int x){
    int st=INF,ed=0;
    for(int i=1;i<n;i++){
        if(h[i]>=x){
            st=min(st,sa[i]);
            ed=max(ed,sa[i]);
            if(ed-st>=x)
                return 1;
        }
        else{
            st=sa[i];
            ed=sa[i];
        }
    }
    return 0;
}
int main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    SF("%d",&n);
    while(n){
    int x,y;
    SF("%d",&x);
    for(int i=0;i<n-1;i++){
        SF("%d",&y);
        r[i]=x-y+90;
        x=y;
    }
    r[n-1]=0;
    //PF("start da\n");
    da();
    //PF("end da\n");
    for(int i=0;i<n;i++)
        ra[sa[i]]=i;
    //PF("start he\n");
    height();
    //PF("end he\n");
    int l=0,r=n;
    while(l<r){
        //PF("(%d %d)\n",l,r);
        int mid=(l+r+1)/2;
        if(check(mid)){
            l=mid;
            ans=max(ans,mid);
        }
        else{
            r=mid-1;
        }
    }
    if(ans+1<5)
        PF("0\n");
    else
        PF("%d\n",ans+1);
    SF("%d",&n);
    ans=0;
    }
}