xrr 的博客

xrr 的博客

OI 从入门到入土

后缀数组

posted on 2018-07-16 16:35:31 | under 字符串算法 |

后缀数组是后缀数的简化版,也是一种非常有用的字符串算法。它是一种拿文本串的后缀与模式串匹配的算法。

我们先简单介绍一下后缀树,它是一个由字符串s的所有后缀组成的一颗Trie树。

像这样

后缀树

(辣鸡网页不给我图)

我们可以看到,这很像就是一颗Trie树,我们在拿模式串来匹配的时候,就可以判断模式串是不是其子串。

然而,这是一种比较麻烦的算法,由于其构造算法比较难懂,且容易写错(后缀数组也没好写到哪里)所以就不说了(其实我也没学)

所以接下来就看看后缀数组吧!!!

我们先来看一个例子:

我们有一个字符串ababa

那么它的后缀就有ababa,baba,aba,ba,a

我们将其按照大小排序(用字符串的排序方式)后就是

名次      起点(即编号)
1:a       5
2:aba     3
3:ababa   1
4:ba      4
5:baba    2

这时,我们要找某个模式串是否是该串的子串,其实就是找是否是该串的后缀的前缀听起来比较绕,但就是这样。比如说子串ab就是第2、第3后缀的前缀,我们也就知道了其起点位置。

那么我们该怎么在后缀树组里进行子串的查找呢?

首先要明白,教我们的后缀数组的数组到底是什么。

这个数组的含义是排在第几的后缀的起点在哪里,其实不难发现,这样一个有序的数组查找时可以二分查找的。

所以,我们先来看一下查找代码,排序代码放在后面

int m
int cmp_suffix(char *pattern ,int p){
    return strncmp(pattern,s+sa[p],m);//c风格的代码比较,具体用法见下。
    //本句比较了从p开始的长度为m的子串与模式串的大小
}

int find(char *p){
    m=strlen(p);
    if(cmp_suffix(p,0)<0) return -1;//比最小的小
    if(cmp_suffix(p,n-1)>0) return -1;//比最大的大
    int l=0,r=n-1;//l为左边界,r为右边界
    while(r>=l){
        int mid=(l+r)>>1;//二分找的起点
        int res=cmp_suffix(p,mid);//当前与mid的大小关系,可以二分
        if(res==0) return mid;//找到了(如果要输出所有位置,可以修改)
        if(res<0) r=mid-1;
        else l=mid+1;
    }
    return -1;//查完了也没有
}

看一下strncmp

strncmp(char *s,char *s',len);
比较从s开始长度为len的子串与从s'开始的长度为len子串,
如果前者大于后者,则返回大于0的值,
若相等则返回0,
若小于则返回小于0的值。

strncmp c++ reference

很妙是不是,所以排序就显得格外重要,因为这是使用二分查找的前提。

接下来我们来讲排序(内容较繁琐,如有不适这请做好准备)

先来一个排序的分析(可以跳过)

对于所有的排序来说,我们都有两个步骤,一是比较(判断大小),二是交换(将小的与大的交换)。

在这里,我们来看一下我们学过的排序:

  1. 选择排序

  2. 冒泡排序

  3. 快速排序

  4. 插入排序

  5. 归并排序

  6. 桶排序

  7. 基数排序

  8. 堆排序

排序全分析

在这之中最快的应该是桶排序,然后是快速排序和归并排序,最后是剩下的几个。

桶排序之所以快是因为它的比较与交换非常快(几乎没有)但是它的空间太大,属于用空间换时间的排序,在数据范围小的情况下适用,它的时间复杂度是O(n)

然后是快排,归并,堆排等O(nlog2n)

最后是选择,冒泡,插入等O(n^2)

注意,这里说的都是平均情况,而且上面的排序由于是对数字进行比较与排序,所以他们的比较都是O(1)

在上面的排序中,有一个十分特殊的排序,就是基数排序。

它是桶排序的变式

这个排序它的时间复杂度是O(n * m)(m是位数)

m是比较时间,n是交换时间,所以在某些地方它还是很快的。

我们回归正题(不要跳了)

我们在这里的排序十分特殊,因为字符串的比较与数字不同,字符串的比较是O(m)(m是位数)。

所以上面的所有排序(除了基数排序)的复杂度都要乘以m。

而对于一个后缀数组来说,它的最长位数等于后缀数量,即m==n。

所以上面的快速排序等,就变成了O(n^2log2n)

而基数排序,在数字间的排序之所以慢,是因为它将O(1)的比较变成了O(m)

而在这里,不管对什么排序来说,比较都是O(m),基数排序的优势就出来了。

而我们这里的基排在O(n)的比较上进行了优化,将其优化到O(log2n)。

这里使用的是倍增基排

我们先提一个概念,二元组,即(a,b)的一个有序对。我们对二元组比较时,先比第一关键字也就是a,相同时,再比较第二关键字也就是b。

我们第一次用每个的第一位字母排序(这里其实也是一个二元组,其第二关键字是原顺序),然后用每一个后缀的前两个字母的新顺序组成一个二元组,其第一关键字是前一个字母,第二关键字是后一个字母。用这个二元组进行排序(基排)我们得到了二元组的顺序(相同二元组名次相同)

到这里应该还能懂,如果不懂再看几遍。

然后第二次排序和第一次排序基本一样,我再复述一遍。

我们第二次用每个后缀的第一次排序的二元组大小序号该后缀起点编号加二的后缀的第一次排序的二元组大小分别作为第一和第二关键字。这样其实我们就将按该后缀的前四个字母进行排序。其第一关键字是前二个字母的大小,第二关键字是后二个字母的大小。

之后第n次排序是用第n-1次排序的二元组的大小和该后缀起点编号加(2^(n-1))的后缀的二元组作为第一和第二关键字。

如下图,rank是该二元组的大小排名

x是第一关键字的排名,y是第二关键字的排名

当每个二元组的排名两两互不相同时其二元组顺序就是该后缀的大小顺序(因为每个的长度都互不相同,所以其大小也互不相同)

具体过程如下

倍增基排

接下来我们附上一个很难懂得代码(其实都一样),以及很长的注释(不然看不懂,我看了足足一个半小时(不看解释,只看代码))

这里先解释一下个数组的用处:

  1. sa代表着当前排完序后第i小的后缀的起点在哪(不一定是最终结果)
  2. t也就是x代表着编号为i的第一关键字的排序大小
  3. t2代表着第二关键字大小为i的编号
  4. c是基数排序的辅助数组
  5. m是第一关键字的数量(最大的那个的下标)

如果注释看不懂可以看下面的分步解释

#include<bits/stdc++.h>//万能头是个好东西
using namespace std;
int sa[1000010],t[1000010],t2[1000010],c[1000010],n,m;
string s;

void build(){
    int *x=t,*y=t2;
    memset(c,0,sizeof(c));
    for(int i=0;i<n;i++){
        c[x[i]=s[i]]++,m=max(m,x[i]+1);//按后缀的第一个字符排序;
    }
    for(int i=1;i<m;i++){
        c[i]+=c[i-1];//基术排序的前缀和使得对于i<j时的(i,j)来说,以i为第一关键字的后缀的顺序大小一定比以j为第一关键字的顺序大小小。
    }
    for(int i=n-1;i>=0;i--){
        sa[--c[x[i]]]=i;//第一次排完序后的顺序
    }
    for(int k=1;k<=n;k<<=1){//倍增的过程,k代表着比较前2*k位
        int p=0;//第二关键字的序列
        for(int i=n-k;i<n;i++){
            y[p++]=i;//因为从第n-k开始第二关键字就是空的,比任何数小,所以放前面
        }
        for(int i=0;i<n;i++){
            if(sa[i]>=k){
                y[p++]=sa[i]-k;//将上一次的排序后的顺序(因为排名为i的后缀sa[i]是按前k个字母排,而这个顺序是是sa[i]-k的第二关键字),如果不懂看下
            }
        }
        memset(c,0,sizeof(c));//辅助数组清零
        for(int i=0;i<n;i++){
            c[x[y[i]]]++;//基数排序,与前面那一小段相同
        }
        for(int i=0;i<m;i++){
            c[i]+=c[i-1];//基数前缀和,使得i越小排名越小,不管你i的数量与i-1的数量有怎样关系,只要不为零,第一关键字取i-1的后面的顺序一定比第一关键字取i的小
        }
        for(int i=n-1;i>=0;i--){
            sa[--c[x[y[i]]]]=y[i];//新顺序,这里因为x[i]是以i为编号的后缀的第一关键字的大小
                                  //而y[i]是第二关键字为第i名的编号,这一句话使得
                                  //对于第一关键字不同的来说肯定第一关键字越小排名越靠前
                                  //对于第一关键字相同的来说,第二关键字越靠后的排名越靠后
        }
        int *tmp=y;
        y=x;
        x=tmp;//此时第二关键字已不再需要,将它舍弃,而新的第一关键字排序仍需这次的第一关键字作为相同的判断条件,所以交换
        p=1;//p-1作为新排名(从0开始)
        x[sa[0]]=0;//最小的排名肯定为0
        for(int i=1;i<n;i++){
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] ? p-1:p++);
            //如果该后缀的第一关键字等于前一个的第一关键字
            //且该后缀的第二关键字等于前一个的第二关键字(后缀i的第二关键字其实是后缀i+k的第一关键字)
            //p不变,该后缀与前一个的后缀的当前二元组的实际排名相同
        }
        if(p>=n) return;
        m=p;//更新第一关键字数量
    }
}

int main(){
    cin>>s;
    n=s.size();
    build();
    for(int i=0;i<n;i++) cout<<sa[i]+1<<" ";
    return 0;
}

如果看不懂上面的,我们来分步解释

1.我们要根据第一个字母作为第一关键字,顺序为第二关键字排序

小代码:

int *x=t,*y=t2;
    memset(c,0,sizeof(c));
    for(int i=0;i<n;i++){
        c[x[i]=s[i]]++,m=max(m,x[i]+1);
    }
    for(int i=1;i<m;i++){
        c[i]+=c[i-1];
    }
    for(int i=n-1;i>=0;i--){
        sa[--c[x[i]]]=i;
    }
memset(c,0,sizeof(c));

第一句 清空c,后面要用,不解释

for(int i=0;i<n;i++){
    c[x[i]=s[i]]++,m=max(m,x[i]+1);
}

第二句,一个循环,我们每出现一次该字符,就将它的数量加加,使总排名为每一个第一关键字为x[i]的都留出顺序空间,例如 ababa 中第一个字母为a的后缀有三个,就为这三个后缀留出三个空位,增加计数。

for(int i=1;i<m;i++){
    c[i]+=c[i-1];
}

第三句,又一个循环 %¥&@¥#@¥&¥%#

看表面它将c球类一个前缀和,为什么呢?因为若i<j则第一关键字为i的前缀一定小于第一关键字为j的前缀。我们就将j的数量加到i里面,这样就使得j的名次一定大于i,一直加下去,使得后面的一直大于前面的

以ababa为例,在这里前缀和之前,你得到的是:

c[a]=3;
c[b]=2;

前缀和后得到的是:

c[a]=3;
c[b]=5;

没看出来?那我们来看一下第四句

for(int i=n-1;i>=0;i--){
    sa[--c[x[i]]]=i;
}

第四句,我们用上基数排序的知识,以i(即序列先后)为第二关键字,x[i]为第一关键字排序。

对于x[i]不同的来说,第三句那个前缀和保证了x[i]的大小一定延续到新的sa序中

(因为c数组,每一个x[i]都已经被分块,比如说 ababa中,开头为a的有三个,会被从3减到2,1,0。

而第一关键字为a的后缀的排名一定在0,1,2这三个排名里,开头为b的有两个,c[b]就会被从5减到4,3。

同样,以b为第一关键字的后缀的排名一定在3,4中)

而i从后向前遍历,保证对于每个相同的x[i]来说i越靠后,新排名越靠后。

为什么呢? 因为当x[i]取到时,c[x[i]]会自减,而下一次取到x[i]时,i肯定比上一次小,而c[x[i]]也减小了,所以保证了第二关键字的排序。

注意了,这里的sa是排名为i的后缀是哪个

这样我们第一次的处理好了,如果你理解的这些,后面的也更好理解了。

2.我们开始按照k(即选取的前多少个字母的个数除以二)倍增来循环

为什么k是个数除以二呢?

因为k是关键字在字符串里的长度

i加上k跳过了当前的第一关键字,来调用第二关键字,见下举例

我们看

ababa
在k为1时,后缀1的第二关键字是后缀1+k=2的第一关键字,即a|b|aba(竖线中间的为第二关键字)
在k为2时,后缀1的第二关键字是后缀1+k=3的第一关键字,即ab|ab|a

懂了没?如果没有,可以加长串长并多枚举几个k来看看

3.懂了k之后,我们来看一下这时怎么处理第二关键字

小代码:

int p=0;
for(int i=n-k;i<n;i++){
    y[p++]=i;
}
for(int i=0;i<n;i++){
    if(sa[i]>=k){
        y[p++]=sa[i]-k;
    }
}
int p=0;

第一句 将排名从0开始

for(int i=n-k;i<n;i++){
    y[p++]=i;
}

第二句 将第二关键字为空(因为从n-k开始的后缀的第二关键字为从n开始的第一关键字,而字符串只到n-1,所以为空)的按原顺序放在最前面(保证有序)

for(int i=0;i<n;i++){
    if(sa[i]>=k){
        y[p++]=sa[i]-k;
    }
}

第三句 将第二关键字不为空的后缀按第二关键字排序。

因为sa[i]内是第一关键字的排序,而第i名的第一关键字是其编号减去k的后缀的第二关键字,所以这时sa[i]即编号也要大于k

4.我们来基数排序第一关键字

小代码:

memset(c,0,sizeof(c));
for(int i=0;i<n;i++){
    c[x[y[i]]]++;
}
for(int i=0;i<m;i++){
    c[i]+=c[i-1];
}
for(int i=n-1;i>=0;i--){
    sa[--c[x[y[i]]]]=y[i];
}

这里的代码和前面的很像就是按照第一二关键字排序

先将这些后缀按第一关键字压入桶中再按照第二关键字提出桶的前缀和保证其在第一关键字上的先后,按照第二关键字提出,保证了其在第二关键字上的先后排序。

就是基排的作法

不会的再理解一下基排或者画一下这个桶的图,具体过程手画下就应该能明白了

5.更新下一次的第一关键字

小代码:

int *tmp=y;
    y=x;
    x=tmp;
    p=1;
    x[sa[0]]=0;
    for(int i=1;i<n;i++){
        x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] ? p-1:p++);
//或改成下面这几句
//      if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]){
//          x[sa[i]]=p-1;
//      }
//      else x[sa[i]]=p++;
    }

这段代码极为玄学

同样画了图会更清晰。

因为x和y是交换过的,我们现在的y就是编号为i的后缀前k个字符的大小顺序,如果y[sa[i]]==y[sa[i-1]]即当前后缀的前k个字符和前一个后缀的前k个字符相等,

y[sa[i]+k]==y[sa[i-1]+k]同理,因为i+k后缀的前k个字符是i后缀的k+1~2 k的字符,若这两个都相同,即表示后缀sa[i]与sa[i-1](这两个数组的值为编号)的前2 k个字符相等。

至于为什么用sa[i]来做为编号呢?

因为我们在基排的时候,前2* k位相等的肯定靠在一起,如果sa[i]与sa[i-1]不相等,与sa[i+1]也不相等,那就不用比别的了。所以只需判大小相邻的是否相等就行了。

这在下一次判断第一关键字是否相等时有用

这一段代码总的来说可以如下描述:

如果这2 * k个字符相等那么该后缀和前一个后缀的二元组应该相等都是p-1,若不相等则个数,也就是名次p要自增

6.更新第一关键字种类数量并判断是否已经排完

小代码:

if(p>=n) return;
        m=p;

如果第一关键字种类数量和后缀数相同则已经排完

我们再看一下总代码,再自己理解一下

#include<bits/stdc++.h>
using namespace std;
int sa[1000010],t[1000010],t2[1000010],c[1000010],n,m;
string s;

void build(){
    int *x=t,*y=t2;
    memset(c,0,sizeof(c));
    for(int i=0;i<n;i++){
        c[x[i]=s[i]]++,m=max(m,x[i]+1);
    }
    for(int i=1;i<m;i++){
        c[i]+=c[i-1];
    }
    for(int i=n-1;i>=0;i--){
        sa[--c[x[i]]]=i;
    }
    for(int k=1;k<=n;k<<=1){
        int p=0;
        for(int i=n-k;i<n;i++){
            y[p++]=i;
        }
        for(int i=0;i<n;i++){
            if(sa[i]>=k){
                y[p++]=sa[i]-k;
            }
        }
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++){
            c[x[y[i]]]++;
        }
        for(int i=0;i<m;i++){
            c[i]+=c[i-1];
        }
        for(int i=n-1;i>=0;i--){
            sa[--c[x[y[i]]]]=y[i];
        }
        int *tmp=y;
        y=x;
        x=tmp;
        p=1;
        x[sa[0]]=0;
        for(int i=1;i<n;i++){
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] ? p-1:p++);
        }
        if(p>=n) return;
        m=p;
    }
}

int main(){
    cin>>s;
    n=s.size();
    build();
    for(int i=0;i<n;i++) cout<<sa[i]+1<<" ";
    return 0;
}

后缀数组的排序和查询都讲了,结合一下就行了。

如果还没懂可以走这里

小青蛙的传送门

如果你已经懂了,走这里,这儿有着后缀数组一个更为秒的应用

LCP(最长公共前缀)——后缀数组的延续