洛谷P3975 [TJOI2015]弦论后缀数组&&暴力

后缀数组&&暴力

大佬曾经曰过：可以拿所有后缀的所有前缀来表示字符串的所有子串。

后缀数组提供了一种按字典序线性(不重复)遍历所有子串的方法。

ps.符号参考博客https://xminh.github.io/2018/02/27/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84-%E6%9C%80%E8%AF%A6%E7%BB%86(maybe)%E8%AE%B2%E8%A7%A3.html

分两层遍历，第一层以sa为基准(从1到n,按后缀字典序遍历每个后缀)，第一层内以height为基准(从height[i]+1到height[i+1])。

跑完一层suff(sa[i])之后，所有字典序不大于suff(a[i])的子串都已遍历完毕。

suff(sa[]) height[]

... ......

aabbbc 0

aabcc 3

aabccd 5

... ......

假设某连续的sa数组代表的suff如上，遍历顺序显然为：[a,a,a],[aa,aa,aa][aab,aab,aab]{aabb,aabbb,aabbbc}

　　　　　　　　　　　　 [aabc,aabc][aabcc,aabcc]

　　　　　　　　　　　　 {aabccd}

在本题中，将公共的前缀(比剩余部分字典序小的)贡献添加给base，再把字符串剩余部分的贡献加给base。就跑完了所有字典序小于等于suff(sa[i])的子串。(如果height[i+1]>=sa[i], height[i+2]>=sa[i]...,就把suff(sa[i+1])和suff(sa[i+1])...的字典序等于suff(sa[i])的部分跑完，并且累计贡献,终点为min(sa[i],height[i+1]))，

即在遍历suff(sa[k])之前，suff(sa[k])长度小于等于height[k]的前缀的贡献已在遍历某个suff(sa[j]),j<k时计算完毕。

时间复杂度log(n)的方法：不会。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

const int maxn = 5e5+4;

char s[maxn];
int x[maxn], y[maxn], c[maxn], rk[maxn], sa[maxn], height[maxn], p[maxn];
int n, m = 'z'+1, N, k;

void get_sa()
{
    for(int i = 1; i <= n; i++) c[x[i] = s[i]]++;
    for(int i = 2; i <= m; i++) c[i] += c[i-1];
    for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;

    for(int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for(int i = n-k+1; i <= n; i++) y[++num] = i;
        for(int i = 1; i <= n; i++) if(sa[i] > k) y[++num] = sa[i] - k;
        for(int i = 1; i <= m; i++) c[i] = 0;
        for(int i = 1; i <= n; i++) c[x[i]]++;
        for(int i = 2; i <= m; i++) c[i] += c[i-1];
        for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1; num = 1;
        for(int 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;
        
        if(num == n) break;
        m = num;
    }
}

void get_height()
{
    int k = 0;
    for(int i = 1; i <= n; i++) rk[sa[i]] = i;
    for(int i = 1; i <= n; i++)
    {
        if(rk[i] == 1) continue;
        if(k) k--;
        int 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]];
    }
}

int main()
{
    scanf("%s", s+1);
    n = strlen(s+1);
    scanf("%d%d",&k, &N);
    get_sa();
    get_height();
    int base = 0;
    if(!k)
    for(int i = 1; i <= n; i++)
    {
        base += n - sa[i] + 1 - height[i];
        if(base >= N)
           {for(int j = sa[i]; j <= n - (base-N); j++) printf("%c", s[j]);puts("");break;}
    }
    else
    for(int i = 1, flag = 0; i <= n && !flag; i++)
    {
        for(int t1 = height[i]+1; t1 <= height[i+1] && !flag; t1++) 
        {
            int t2 = i;base++;
            while(height[t2+1] >= t1) base++,t2++;
            if(base >= N) for(int j = sa[i]; j < sa[i]+t1; j++) {printf("%c",s[j]);puts("");flag = 1;}
        }
        base += n - sa[i] + 1 - max(height[i], height[i+1]);
        if(!flag && base >= N) 
            {for(int j = sa[i]; j <= n - (base-N); j++) printf("%c", s[j]);puts("");break;}
    }
    if(base < N) puts("-1");
    return 0;
}

洛谷P3975 [TJOI2015]弦论 后缀数组&&暴力

洛谷P3975 [TJOI2015]弦论后缀数组&&暴力