后缀数组新手向入门

xMinh · 2018-07-14 16:40:03 · 个人记录

后缀数组新手向入门

后缀数组这个东西真的是神仙操作……

但是这个比较神仙的东西在网上的讲解一般都仅限于思想而不是代码，而且这个东西开一堆数组，很多初学者写代码的时候很容易发生歧义理解，所以这里给出一个比较详细的讲解。笔者自己也是和后缀数组硬刚了一个上午外加一个中午才理解的板子。

本人版权意识薄弱，如有侵权现象请联系博主邮箱[email protected]

参考文献见文末

什么是后缀数组

我们先看几条定义：

子串

在字符串s中，取任意i<=j，那么在s中截取从i到j的这一段就叫做s的一个子串

后缀

后缀就是从字符串的某个位置i到字符串末尾的子串，我们定义以s的第i个字符为第一个元素的后缀为suff(i)

后缀数组

把s的每个后缀按照字典序排序，

后缀数组sa[i]就表示排名为i的后缀的起始位置的下标

而它的映射数组rk[i]就表示起始位置的下标为i的后缀的排名

简单来说，sa表示排名为i的是啥，rk表示第i个的排名是啥

一定要记牢这些数组的意思，后面看代码的时候如果记不牢的话就绝对看不懂

后缀数组的思想

先说最暴力的情况，快排O(n log n)每个后缀，但是这是字符串，所以比较任意两个后缀的复杂度其实是O(n)，这样一来就是接近O(n^2 log n)的复杂度，数据大了肯定是不行的，所以我们这里有两个优化。

ps：本文中的^表示平方而不是异或

倍增

首先读入字符串之后我们现根据单个字符排序，当然也可以理解为先按照每个后缀的第一个字符排序。对于每个字符，我们按照字典序给一个排名(当然可以并列)，这里称作关键字。

接下来我们再把相邻的两个关键字合并到一起，就相当于根据每一个后缀的前两个字符进行排序。想想看，这样就是以第一个字符(也就是自己本身)的排名为第一关键字，以第二个字符的排名为第二关键字，把组成的新数排完序之后再次标号。没有第二关键字的补零。

既然是倍增，就要有点倍增的样子。接下来我们对于一个在第i位上的关键字，它的第二关键字就是第(i+2)位置上的，联想一下，因为现在第i位上的关键字是suff(i)的前两个字符的排名，第i+2位置上的关键字是suff(i+2)的前两个字符的排名，这两个一合并，不就是suff(i)的前四个字符的排名吗？方法同上，排序之后重新标号，没有第二关键字的补零。同理我们可以证明，下一次我们要合并的是第i位和第i+4位，以此类推即可……

ps：本文中的“第i位”表示下标而不是排名。排名的话我会说“排名为i”

那么我们什么时候结束呢？很简单，当所有的排名都不同的时候我们直接退出就可以了，因为已经排好了。

显然这样排序的速度稳定在O(log n)

基数排序

如果我们用快排的话，复杂度就是O(n log^2 n) 还是太大。

这里我们用一波基数排序优化一下。在这里我们可以注意到，每一次排序都是排两位数，所以基数排序可以将它优化到O(n)级别，总复杂度就是O(n log n)。

介绍一下什么是基数排序，这里就拿两位数举例

我们要建两个桶，一个装个位，一个装十位，我们先把数加到个位桶里面，再加到十位桶里面，这样就能保证对于每个十位桶，桶内的顺序肯定是按个位升序的，很好理解。

写SA的过程中我们把第一关键字看做十位，第二关键字看做个位。

最长公共前缀——后缀数组的辅助工具

话说这个费了我好长时间，就为了证明几条定理……懒得证明的话背过就行了，不过笔者还是觉得知道证明用起来更踏实一些，话说我的证明过程应该比较好懂，适合初学者理解……

什么是LCP？

我们定义LCP(i,j)为suff(sa[i])与suff(sa[j])的最长公共前缀

为什么要求LCP？

后缀数组这个东西，不可能只让你排个序就完事了……大多数情况下我们都需要用到这个辅助工具LCP来做题的

关于LCP的几条性质

显而易见的

LCP(i,j)=LCP(j,i)
LCP(i,i)=len(sa[i])=n-sa[i]+1

这两条性质有什么用呢？对于i>j的情况，我们可以把它转化成i<j，对于i==j的情况，我们可以直接算长度，所以我们直接讨论i<j的情况就可以了。

我们每次依次比较字符肯定是不行的，单次复杂度为O(n)，太高了，所以我们要做一定的预处理才行。

LCP Lemma

LCP(i,k)=min(LCP(i,j),LCP(j,k)) 对于任意1<=i<=j<=k<=n

证明：设p=min(LCP(i,j),LCP(j,k))，则有LCP(i,j)≥p,LCP(j,k)≥p

设suff(sa[i])=u,suff(sa[j])=v,suff(sa[k])=w

所以u和v的前p个字符相等，v和w的前p个字符相等

所以u和w的前p的字符相等，LCP(i,k)>=p

设LCP(i,k)=q>p 那么q>=p+1

因为p=min(LCP(i,j),LCP(j,k))，所以u[p+1]!=v[p+1] 或者 v[p+1]!=w[p+1]

和u[p+1]=w[p+1] 这不就自相矛盾了吗

所以LCP(i,k)<=p

综上所述LCP(i,k)=p=min(LCP(i,j),LCP(j,k))

LCP Theorem

LCP(i,k)=min(LCP(j,j-1)) 对于任意1<i<=j<=k<=n

这个结合LCP ~~Lemma就很好理解了

我们可以把i~k拆成两部分i~(i+1)以及(i+1)~k

那么LCP(i,k)=min(LCP(i,i+1),LCP(i+1,k))

我们可以把(i+1)~k再拆，这样就像一个DP，正确性显然

怎么求LCP？

我们设height[i]为LCP(i,i-1)，1<i<=n，显然height[1]=0

由LCP ~~Theorem可得，LCP(i,k)=min(height[j])， i+1<=j<=k

那么height怎么求，枚举吗？NONONO，我们要利用这些后缀之间的联系

设h[i]=height[rk[i]]，同样的，height[i]=h[sa[i]]

我们可以理解为，h[i]表示suffix(i)和排名在他前面的后缀的LCP

那么现在来证明最关键的一条定理：

h[i]>=h[i-1]-1

首先我们不妨设第i-1个字符串按排名来的前面的那个字符串是第k个字符串，注意k不一定是i-2，因为第k个字符串是按字典序排名来的i-1前面那个，并不是指在原字符串中位置在i-1前面的那个第i-2个字符串。

这时，依据height的定义，第k个字符串和第i-1个字符串的公共前缀自然是height[rk[i-1]]，现在先讨论一下第k+1个字符串和第i个字符串的关系。

第一种情况，第k个字符串和第i-1个字符串的首字符不同，那么第k+1个字符串的排名既可能在i的前面，也可能在i的后面，但没有关系，因为如果不同的话height[rk[i-1]]就是0，那么无论height[rk[i]]是多少都会有height[rk[i]]>=height[rk[i-1]]-1

第二种情况，第k个字符串和第i-1个字符串的首字符相同，那么由于第k+1个字符串就是第k个字符串去掉首字符得到的，第i个字符串也是第i-1个字符串去掉首字符得到的，那么显然第k+1个字符串要排在第i个字符串前面。就相当于第k个和第i-1个字符串同时去掉一个首字母，所以LCP(rk[i],rk[k+1])就是height[rk[i-1]]-1

到此为止，第二种情况的证明还没有完，我们可以试想一下，对于比第i个字符串的排名更靠前的那些字符串，谁和第i个字符串长得最像？显然是排名紧邻第i个字符串的那个字符串了呀，即sa[rk[i]-1]

所以LCP(rk[i],rk[i]-1)>=LCP(rk[i],rk[k+1])-1

等量代换 height[rk[i]]>=height[rk[i-1]]-1

也就是h[i]>=h[i-1]-1

在实现的时候，我们没有必要保存h数组，只需要按着h[1],h[2],……,h[n]的顺序计算就好了

代码(详细注释)

例题：luogu3809 后缀排序

注意上面那个题不用求lcp……看代码建议先大略扫一遍，因为的确有点绕

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define ini inline int
#define maxn 1000050
using namespace std;
char s[maxn];
int y[maxn],x[maxn],c[maxn],sa[maxn],rk[maxn],height[maxn],wt[30];
int n,m;
inv putout(int x)
{
    if(!x) {putchar(48);return;}
    rint l=0;
    while(x) wt[++l]=x%10,x/=10;
    while(l) putchar(wt[l--]+48);
}
inv get_SA()
{
    for (rint i=1;i<=n;++i) ++c[x[i]=s[i]];
    //c数组是桶 
    //x[i]是第i个元素的第一关键字 
    for (rint i=2;i<=m;++i) c[i]+=c[i-1]; 
    //做c的前缀和，我们就可以得出每个关键字最多是在第几名 
    for (rint i=n;i>=1;--i) sa[c[x[i]]--]=i; 
    for (rint k=1;k<=n;k<<=1)
    {
        rint num=0;
        for (rint i=n-k+1;i<=n;++i) y[++num]=i;
        //y[i]表示第二关键字排名为i的数，第一关键字的位置 
       //第n-k+1到第n位是没有第二关键字的 所以排名在最前面 
        for (rint i=1;i<=n;++i) if (sa[i]>k) y[++num]=sa[i]-k;
        //排名为i的数 在数组中是否在第k位以后
        //如果满足(sa[i]>k) 那么它可以作为别人的第二关键字，就把它的第一关键字的位置添加进y就行了
        //所以i枚举的是第二关键字的排名，第二关键字靠前的先入队 
        for (rint i=1;i<=m;++i) c[i]=0;
        //初始化c桶 
        for (rint i=1;i<=n;++i) ++c[x[i]];
        //因为上一次循环已经算出了这次的第一关键字 所以直接加就行了 
        for (rint i=2;i<=m;++i) c[i]+=c[i-1];//第一关键字排名为1~i的数有多少个 
        for (rint i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
        //因为y的顺序是按照第二关键字的顺序来排的 
        //第二关键字靠后的，在同一个第一关键字桶中排名越靠后 
        //基数排序 
        swap(x,y);
        //这里不用想太多，因为要生成新的x时要用到旧的，就把旧的复制下来 
        x[sa[1]]=1;num=1;
        for (rint i=2;i<=n;++i)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
        //因为sa[i]已经排好序了，所以可以按排名枚举，生成下一次的第一关键字 
        if (num==n) break;
        m=num;
        //这里就不用那个122了，因为都有新的编号了 
    }
    for (rint i=1;i<=n;++i) putout(sa[i]),putchar(' ');
}
inv get_height()
{
    rint k=0;
    for (rint i=1;i<=n;++i) rk[sa[i]]=i;
    for (rint i=1;i<=n;++i)  
    {
        if (rk[i]==1) continue;//第一名height为0 
        if (k) --k;//h[i]>=h[i-1]-1;
        rint j=sa[rk[i]-1];
        while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
        height[rk[i]]=k;//h[i]=height[rk[i]];
    }
    putchar(10);for (rint i=1;i<=n;++i) putout(height[i]),putchar(' ');
}
int main()
{
    gets(s+1);
    n=strlen(s+1);m=122;
    //因为这个题不读入n和m所以要自己设
    //n表示原字符串长度，m表示字符个数，ascll('z')=122 
    //我们第一次读入字符直接不用转化，按原来的ascll码来就可以了 
    //因为转化数字和大小写字母还得分类讨论，怪麻烦的 
    get_SA();
    //get_height();
}

例题

在罗穗骞大神的09年集训队论文《后缀数组——处理字符串问题的有力工具》中，有许多有意义的后缀数组例题，但是为了避免对论文的一味复制，以及更适应新手阅读，我主要讲一下几个思想，推荐几道个人认为比较有意义的真题。

分组思想

顾名思义，就是把sa数组分组处理，一般与二分相结合。

不可重叠最长重复子串(pku1743)

给出一个旋律，用n个数字[1,88]表示其音符，求它的最长的主题长度;

一个旋律的主题是一段至少出现过两次的不重叠音乐片段;

重复出现也包括一段音乐全体加上某个数后再次出现(如1 2 3 4 5和5 6 7 8 9为同一个音乐片段，全部+4);

主题长度至少为5,无解输出0

解析

先逐差

然后二分答案，二分出一个长度k，从头到尾按排名扫所有后缀，在这个过程中把所有后缀分组，满足每一组之间两两height不小于k——这样就可以保证分组是顺序分的，而且满足条件的两个后缀一定在同一组。这样我们只需要按排名从头到尾扫后缀，如果同一组里面任意一对后缀的SA的极差>=k就可以了。

这个可以自己画图理解一下，也可以参考论文。

分组思想的题目还有：

可重叠的k 次最长重复子串（pku3261）

不小于k个字符串中的最长子串(pku3294)

都大同小异，可以自己尝试一下

分隔思想

顾名思义，就是打分隔符标记。

最长公共子串(pku2774,ural1517)

给定两个字符串A和B,求最长公共子串。

解析

把两个串连在一起，中间打分隔符

求suff(sa[i])和suff(sa[i-1])不在同一个串时的height最大值

多个串就是SDOI2008 Sandy的卡片

分隔思想的题目还有：

基本涉及多个字符串的题目都会用到分隔符

最长回文子串(ural1297)

还有一道看起来像是计算几何的题目：[POI2007]OSI-Axes of Symmetry

数数

不相同的子串的个数(spoj694,spoj705)

给出一个字符串，求不相同的子串个数

解析

对于每个子串我们可以看做后缀的前缀

我们按照排名扫每个后缀

那么每次“后缀的前缀”的总数就会加上n-sa[i]+1个

但是有height[i]个是和前面的重复了

所以每次加上n-sa[i]+1-height[i]就可以了

数数的题目还有：

长度不小于k的公共子串的个数(pku3415)

以及与其它数据结构相结合的SDOI2016 生成魔咒

其它思想？

剩下的就比较零散了

比如求重复子串，公共子串等的一些技巧

考虑到新手向的问题不多讲，但还是要说一句：一定要看论文啊！！！！！！

参考文献：

罗穗骞《后缀数组——处理字符串问题的有力工具》

百度百科_后缀数组

尼采学长的blog

wsy的cnblog

soda的cnblog

I'MJACKY的cnblog

董雨的cnblog

J.K.的cnblog

J_Sure的csdn

后缀数组新手向入门

后缀数组 新手向入门

什么是后缀数组

子串

后缀

后缀数组

后缀数组的思想

倍增

基数排序

最长公共前缀——后缀数组的辅助工具

什么是LCP？

为什么要求LCP？

关于LCP的几条性质

显而易见的

LCP Lemma

LCP Theorem

怎么求LCP？

代码(详细注释)

例题

分组思想

不可重叠最长重复子串(pku1743)

解析

分组思想的题目还有：

分隔思想

最长公共子串(pku2774,ural1517)

解析

分隔思想的题目还有：

数数

不相同的子串的个数(spoj694,spoj705)

解析

数数的题目还有：

其它思想？

参考文献：

后缀数组新手向入门