后缀数组&后缀自动机学习笔记

发表于 | 更新于 | 评论数： | 阅读次数：

今天干了两件事情，学会了后缀数组，搞定了洛谷$AC$数量的问题，以后可以不用洛谷咯！

继续学习、复习算法，下一步是后缀自动机。

后缀数组

这儿有道纯模板题

思路

只学了倍增法，但也折腾了半天。贴一下自己的想法。

既然要对后缀排序，那首先当然要找出所有后缀从第一位开始比较了。

于是一上来就有了下面这段代码：

1
2
3
4
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]=s[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;

妈耶，这一堆数组都是啥

$c[i]: $一个辅助数组，用处见下面注释
$x[i]: $呃，这一步的作用仅仅是记录一下$s[i]$的$ASCII$码值。
$s[i]: $就是给定的字符串啦。
$sa[i]: $当前排名为$i$的后缀，起始位置的下标。

一句话一句话解释。

1
2
3
4
5
6
7
8
9
10
11
for(i=0;i<m;i++)c[i]=0;
//数组清零
for(i=0;i<n;i++)c[x[i]=s[i]]++;
//表示这个地方有个东西（比如字符串"abbcc"），最终结果是c['a']=1,c['b']=2,c['c']=2。
//那其实这里的c数组就是一个桶。
//这里先把第一位排好序。
for(i=1;i<m;i++)c[i]+=c[i-1];
//统计前缀和，方便后续统计排名。
for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
//统计排名的时候要求排名互不相同，于是强制在字符相同的情况下，第一个字母靠前的排名靠前。
//这里倒着循环以满足上述条件。

好了，这步结束之后，第一位比较完了。

先看一个例子：$ababbaba$

第一次排序后：（$97$为$‘a’$的$ASCII$码值)

$i$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$
$x [i]$ $97$ $98$ $97$ $98$ $98$ $97$ $98$ $97$
$sa [i]$ $0$ $2$ $5$ $7$ $1$ $3$ $4$ $6$
$sa[i+1]$ $2$ $5$ $7$ $1$ $3$ $4$ $6$ $0$

根据字典序的思想，在第一位字符相同的情况下应该接着比较下一个位置。也就是基数排序，在第一个字符相等的基础上，更细的分离出第二个字符上的区别。

那么我假设前两个字符都比完了，那么接下来该比较的是前三个字符，前四个字符……
但实际上，在比完前两个字符的情况下，可以直接添加两个字符（第二关键词）到前四个字符，在下一轮添加四个字符（第二关键词）到前八个字符……
这里就可以应用倍增的思想进行比较了。

接下来的代码比较长，分几部分，逐步理解。

1
2
3
4
5
6
for(k=1;k<=n;k<<=1){
    int num=0;
    for(i=n-k;i<n;i++)y[num++]=i;
    for(i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
    ...
}

$y[i]:$ 第二关键词（即第2个，第3,4个，第5,6,7,8个……）的排序，$y[i]=j$表示排名$i$的第二关键词，第一关键词的起始位置为$j$。

$[0,i]$中，后$k$个位置的第二关键词是$0$，所以这是最小的，先加入$y$数组。

然后其他的相应排名为$sa[i]$，前面已经排了$k$个，故排名为$sa[i]-k$。

执行完这段代码后：

$i$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$
$y [i]$ $7$ $1$ $4$ $6$ $0$ $2$ $3$ $5$

接着和第一次几乎一样的排序：

1
2
3
4
5
for(i=0;i<m;i++)c[i]=0;//清空桶
for(i=0;i<n;i++)c[x[i]]++;//扔进桶
for(i=1;i<m;i++)c[i]+=c[i-1];//前缀和
for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
//这里是唯一不一样的地方，起到的作用就是在第一次的基础上对第二关键词排序

执行完这段代码后：

$i$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$
$sa[i]$ $7$ $0$ $2$ $5$ $1$ $4$ $6$ $3$
对应字符串 $a0$ $ab$ $ab$ $ab$ $ba$ $ba$ $ba$ $bb$

然后$y$数组已经光荣完成使命，下一轮的$x$数组由这一轮的$x$数组决定。怎么决定呢？显然，如果两个后缀的第一、二关键字在上一轮排名相同，那么本轮排名也相同；否则不同。于是就有：

1
2
3
4
5
6
std::swap(x,y);//其实是扔掉了y数组
num=1;
x[sa[0]]=0;//排名为0
for(i=1;i<n;i++)x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?num-1:num++;
if(num>=n)break;//排序完成的字符数到了n，也就是没有不同排名的后缀了，那么退出
m=num;//优化一下循环

多次类似倍增后，即可得到结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1000010
char s[N];
int x[N],y[N],sa[N],c[10*N];
int main(){
    int i,k,n,m=10000;
    scanf("%s",s);
    n=strlen(s);
    for(i=0;i<m;i++)c[i]=0;
    for(i=0;i<n;i++)c[x[i]=s[i]]++;
    for(i=1;i<m;i++)c[i]+=c[i-1];
    for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for(k=1;k<=n;k<<=1){
        int num=0;
        for(i=n-k;i<n;i++)y[num++]=i;
        for(i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[y[i]]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
        std::swap(x,y);
        num=1;
        x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?num-1:num++;
        if(num>=n)break;
        m=num;
    }
    for(i=0;i<n;i++)printf("%d ",sa[i]+1);
    return 0;
}

可是光排序似乎做不了什么事呢！

引入一个数组$height[i]$，它代表的意义是，排序第$i$和第$i-1$的两个后缀的最长公共前缀。用符号语言表示就是：$height[i]=LCP(suffix(sa[i]),suffix(sa[i-1]))$。（$suffix(i)$表示以$i$为开头的后缀）

那么如何求这个数组呢？单纯的暴力去求，复杂度是爆炸的$O(n^2)$。

引入$rank[i]$数组，表示$suffix(i)$的排名为$rank[i]$。

设$h[i]=height[rank[i]]$，即$h[i]$表示$suffix(i)$和比$suffix(i)$排名靠前一个的后缀的$LCP$，则有$h[i]\geq h[i-1]-1$（证明略去，手推思考一下就是这么一回事）。故从头枚举$suffix(i)$，递推可以算出$height$数组。

于是就有了这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void geth(){
    int i,j,k=0;
    for(i=0;i<n;i++)rank[sa[i]]=i;
    for(i=0;i<n;i++){
        if(!rank[i]){
            height[0]=k=0;
            continue;
        }
        if(k)k--;
        j=sa[rank[i]-1];
        while(s[i+k]==s[j+k])k++;
        height[rank[i]]=k;
    }
}

学到这里的时候一直不明白这个数组为什么要叫$height$，刚刚才弄明白原来他的意思是后缀$trie$上的从左到右相邻两个末端节点（指代表后缀结束处的节点）$LCA$的深度。

所以就可以用这个特殊的性质解决问题了。

问题1 求LCP(suffix(i),suffix(j))

也就是求$min(height[k]),k∈[i+1,j]$（假设$i$排名靠前）。用$ST$表+$RMQ$或者线段树查询即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void init(int n){
    int i,j;
    for(i=0;i<=n;i++)st[0][i]=height[i];
    for(i=n-1;i;i--)
        for(j=1;(1<<j)+i-1<=n;j++)
            st[j][i]=std::min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
int query(int l,int r){
    int m=0;
    if(l>r)std::swap(l,r);
    l++;
    while((1<<(m+1))<r-l+1)m++;
    return std::min(st[m][l],st[m][r-(1<<m)+1]);
}
void solve(){
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&l,&r);
        if(l==r)printf("%d\n",n-l);
        else{
            l=rank[l];r=rank[r];
            if(l>r)swap(l,r);
            printf("%d\n",query(l+1,r));
        }
    }
}

问题2 求可以重叠的最长重复子串

显然，求出$max(height[i])$即可。

（强迫症贴个代码）

1
2
3
4
void solve(){
    int i,ans=0;
    for(i=0;i<n;i++)ans=max(ans,height[i]);
}

问题3 求不可重叠的最长重复子串

考虑到可以枚举答案且答案具有单调性，故考虑二分答案。

问题转化成：是否存在两个长度为$mid$的相同的串，他们的起始位置相差大于等于$mid$。

在后缀数组中转化成：$LCP(i,j)\geq mid,sa[j]-sa[i]\geq mid$。

于是在$height[i]<mid$的地方设置隔板，在每一个小区间内求出$sa$数组的最大最小值，判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int jud(int x){
    int i,mx=-1e9,mn=1e9;
    for(i=0;i<n;i++){
        if(height[i]<mid)mx=mn=sa[i];
        else{
            mx=max(mx,sa[i]);
            mn=min(mn,sa[i]);
            if(mx-mn>=mid)return 1;
        }
    }
    return 0;
}
void solve(){
    int l=0,r=n,ans=0,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(jud(mid))l=mid+1,ans=mid;
        else r=mid;
    }
    printf("%d",ans);
}

其他

见这里

后缀自动机

此坑待填。