【算法】后缀数组

其实后缀数组是个数据结构啊……但是我习惯学个新东西叫算法了
其实也不是最近才学的,之前3月学过一次,但是印象并不是完全深刻,这次再复习一遍
先安利https://blog.csdn.net/YxuanwKeith/article/details/50636898 五分钟搞懂后缀数组!后缀数组解析以及应用(附详解代码),这篇博客讲的挺好的,特别是height数组的证明
这篇http://www.cnblogs.com/zwfymqz/p/8413523.html 也是不错的,图画的挺明白的,不过代码讲的并不是特别详细
后缀数组是个非常有趣又有用的东西,有两种构建办法,O(nlogn)的倍增法和O(n)的DC3法,但是最常用的还是倍增,因为好写啊。所以这里讲的也是倍增法
我们先从一个个单个字母考虑,这个时候显然他们字典序是第一关键字,在原序列位置是第二关键字,那么我们排个序,就可以得到现在的一个相对排名,这个排名的大小也就是这个字符串字典集的大小
然后我们现在将每个字母后面的关键字和它本身的关键字按照前为第一关键字,后为第二关键字,将它们拼起来,这个时候我们发现我们得到了长度为2的字串的相对顺序

也就是这张图画的了
那么我们既然可以从长度为1的关系推出长度为2的关系,当然也可以从长度为2的推出长度为4的……一直推到我们成功的将所有后缀区分成功停止。最坏的时间复杂度是nlogn的
接下来是整个过程

这是一个大体的算法流程,具体实现呢?
先设几个数组
rak[i]表示原字符串以第i位开头的后缀的排名,sa[i]表示当前排名为i的后缀起点在哪,tp[i]表示第二关键字排第i的它所在后缀起点在哪
那么显然rak[sa[i]] = i, sa[rak[i]] = i
这样我们就可以互相转化了
那么我们就可以先处理出之前的sa数组和之前的tp数组,然后将这两个分别作为第一关键字和第二关键字,去跑个排序,就可以得出新的sa数组,再通过sa得到rak数组
现在我们用快排什么的复杂度都是nlogn,这样太慢了,因为我们有更快的排序——基数排序
基数排序思想和桶排有点相像,但是它要比桶排高明,因为它复杂度是几乎可以达到O(n)的,而且它空间也远远小于桶排
还记得刚才我们说通过两个关键字得到新的顺序吗,基数排序和这个类似,我们每次将一个数截成好几部分,然后我们开个桶,桶的大小称为基数,然后我们用桶排的思想,按照当前比较关键字的大小放到相应的桶,我们就可以得知该关键字某个值有多少个,我们再求一边前缀和,再倒序塞回去,我们默认并保证之前的关键字从小到大排序,这样就得到了几个连续的块,这些块内按照当前考虑的所有关键字严格有序,我们从低位到高位排,因为低位已经保证有序了,对于每次高位更新,都是先插入低位值较大的,而本身目前最高位关键字也是有序的,保证每个最高位关键字都有个属于自己的块,所以目前被考虑的所有关键字才严格有序。这样就能保证排序的正确性了。代码会和构建后缀数组的其他步骤放在一起
那么每次我们倍增的过程相当于新增关键字,先处理好tp数组,有些长度较短的后缀没有第二关键字,我们就认为它们第二关键字是0,剩下的我们按照上一轮的sa[i]来处理,假设我们现在考虑的是长度为w的字串,我们要用它们转移到w << 1的字串,显然tp[i]就等于sa[i] – w,因为sa[i]是当所有子串长度不超过w的时候排名为i的字串,那么w << 1之后,他就会作为sa[i] – w这个位置上的第二关键字,所以tp[i]的起点为sa[i] – w
然后我们再去跑基数排序,求每个位置上的后缀目前的排名,并同时求出字典集大小,直到字典集大小和原字符串长度一样长
luogu P3809【模板】后缀排序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

const int ms = 1000010;

int m = 127, len, s[ms], rak[ms], sa[ms], tp[ms], sz[ms];

inline void re()
{
    char a = getchar();
    while((a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z') || (a >= '0' && a <= '9'))
        s[++ len] = a - 48, a = gch();
}

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        sz[i] = 0;
    for(ri i = 1; i <= len; i ++)
        sz[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        sz[i] += sz[i - 1];
    for(ri i = len; i >= 1; i --)
        sa[sz[rak[tp[i]]] --] = tp[i];/*tp[i]表示第二关键字排i的位置在tp[i]
        rak[tp[i]]就是单纯只按第二关键字排名为i的后缀开头位置 
        这个位置按照第一关键字排序,排名第几
        这样做我们首先保证tp是从大往小走的
        然后又因为基数排序的性质我们把前面的第一关键字按照数值大小丢进新的序列中
        所以这就保证了正确性*/ 
}

int main()
{
    re();
    for(ri i = 1; i <= len; i ++)
        rak[i] = s[i], tp[i] = i;
    rsort(); 
    for(ri w = 1, p = 1; p < len; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = len - w + i;//因为后面这些后缀没有第二关键字,自然按第二关键字排名小
        for(ri i = 1; i <= len; i ++)
            if(sa[i] > w)//如果这个后缀往前走w步,这个位置上的后缀有第二关键字的话 
                tp[++ p] = sa[i] - w;/*因为对于排好序的sa数组,在我们要求w << 1后缀时候
                sa[i]的前w个字符是sa[i - w]接下来的后w个字符,因此我们- w*/
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= len; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
        //比较排名相邻两个串,如果俩关键字相同没必要管,否则++p 
    }
    for(ri i = 1; i <= len; i ++)
        printf("%d ", sa[i]);
}

但是求sa和rak并不是后缀数组最为重要的功能,它真正的用处在与求height数组
我们定义height[i] = lcp(sa[i], sa[i – 1]),h[i] = height[rak[i]], h[i] >= h[i – 1] – 1
这个是为啥呢?
h[i]表示的是以i的开头的后缀和它前一名的后缀的公共前缀,那么我们设sa[k]是sa[i – 1]前一名的后缀,那么显然h[i – 1]是这两者的公共前缀,我们现在都向前一位,变成了sa[k + 1]和sa[i],那么它们就相当于同时砍掉开头的一个字符,它们的公共前缀也就是h[i – 1] – 1,那么对于刚才那个不等式,如果h[i – 1]为0或者1的时候显然成立,否则我们继续假设与i最匹配的后缀为x,那么lcp(sa[k + 1], sa[i]) = h[i – 1] – 1,如果x比k + 1一样或者还要匹配的话,那么h[i] >= h[i – 1] – 1
所以我们可以两句话求出这个height
for(ri i = 1; i <= n; h[rak[i ++]] = k)
for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);

这两句话非常直接,k就是之前的h[i]这个值,我们每次从上次结束的位置继续开始,不停往下找,直到不公共为止
例题
poj 1743 Musical Theme
这个题目是求两个不相重叠的相同字串的最长长度,当然你要先把这个序列差分下,求差分值相同的。我们可以用二分+后缀数组解决这个题,这个题就是利用的height数组的性质,假如height数组有一个连续大于x的区间,那么至少可以保证这个区间所包含的所有后缀有个共同的长度为x的后缀,因为lcp(i, j, k) = min(lcp(i, j), lcp(j, k))
那么这个时候二分答案就很明显了,我们可以二分答案,然后在height数组上找一个长度大于mid值并且的所有数都大于等于mid的这么一个区间,之所以长度要大于mid,是因为我们中间需要留个空不让这两个子串连在一起

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin));
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 20020;

int n, m, l, r, b[ms], s[ms], sa[ms], rak[ms], tp[ms], num[260], h[ms];

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        num[i] = 0;
    for(ri i = 1; i <= n; i ++)
        num[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        num[i] += num[i - 1];
    for(ri i = n; i >= 1; i --)
        sa[num[rak[tp[i]]] --] = tp[i];
}

inline void asksa()
{
    rsort();
    for(ri w = 1, p = 0; p < n; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = n - w + i;
        for(ri i = 1; i <= n; i ++)
            if(sa[i] > w)
                tp[++ p] = sa[i] - w;
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= n; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
    }
    ri k = 0, j;
    for(ri i = 1; i <= n; h[rak[i ++]] = k)
        for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);
}

inline bool check(int x)
{
    int mx = - 1e9 - 7, mi = 1e9 + 7;
    for(ri i = 3; i <= n; i ++)
    {
        if(h[i] >= x)
        {
            mi = min(mi, min(sa[i], sa[i - 1])), mx = max(mx, max(sa[i], sa[i - 1]));
            if(mx - mi > x)
                return 1;
        }
        else
            mx = - 1e9 - 7, mi = 1e9 + 7;
    }
    return 0;
}

int main()
{
    re(n);
    while(n > 0)
    {
        m = 233;
        for(ri i = 1; i <= n; i ++)
            re(b[i]); 
        for(ri i = 1; i < n; i ++)
            s[i] = b[i + 1] - b[i] + 88;
        s[n] = 0;
        for(ri i = 1; i <= n; i ++)
            rak[i] = s[i], tp[i] = i;
        asksa(); l = 0, r = (n - 1) >> 1;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        printf("%d\n", (l >= 4) ? l + 1: 0); re(n);
    }
    return 0;
}

luogu P2852 [USACO06DEC]牛奶模式Milk Patterns
这个题目和刚才大同小异,只不过现在从不可重叠变成了可以重叠,从2个变成了k个,那么我们稍微改改,还是二分一个mid值,然后只要有个长度连续大于k的区间就行
我就改了改check函数和预处理

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin));
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 20020;

int n, m, k, l, r, b[ms], s[ms], sa[ms], rak[ms], tp[ms], num[20060], h[ms];

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        num[i] = 0;
    for(ri i = 1; i <= n; i ++)
        num[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        num[i] += num[i - 1];
    for(ri i = n; i >= 1; i --)
        sa[num[rak[tp[i]]] --] = tp[i];
}

inline void asksa()
{
    rsort();
    for(ri w = 1, p = 0; p < n; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = n - w + i;
        for(ri i = 1; i <= n; i ++)
            if(sa[i] > w)
                tp[++ p] = sa[i] - w;
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= n; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
    }
    ri k = 0, j;
    for(ri i = 1; i <= n; h[rak[i ++]] = k)
        for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);
}

inline bool check(int x)
{
    int mx = 1, mi = 1;
    for(ri i = 2; i <= n; i ++)
    {
        if(h[i] >= x)
            mx ++;
        else
            mi = mx = i; 
        if(mx - mi + 1 >= k)
            return 1;
    }
    return 0;
}

int main()
{
    re(n);
    m = 20000, re(k);
    for(ri i = 1; i <= n; i ++)
        re(s[i]); 
    for(ri i = 1; i <= n; i ++)
        rak[i] = s[i], tp[i] = i;
    asksa(); l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", l);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注