SPOJ7258 SUBLEX - Lexicographical Substring Search（SAM第K大）

题目链接

分析：

SAM S A M 求第 K K 大子串

首先我们建出SAMSAM

假如我们把 SAM S A M 变成一棵 dfs d f s 树

那么每一个结点（代表一个状态）后面都跟着一棵子树，

我们就假设这个结点的状态是 S S ，那么子树中的每一个结点代表的子串一定有SS的前缀

如果我们已经确定了第 K K 个子串的前缀是SS，我们需要确定下一个字符

那么我们就需要知道每个状态后面的子树大小： sumi s u m i

这样我们就可以从小到大枚举当前字符，

如果 sumi>=K s u m i >= K ，说明下一位的字符就是 i i

如果sumi<Ksumi<K，说明下一位的字符肯定大于 i i ，所以K−=sumiK−=sumi，继续向下枚举

那么 sum s u m 数组怎么确定呢

其实很简单，以为在 SAM S A M 上不同的状态仅出现一次，这恰好符合题目要求

所以初始值 sumi=1(sumroot=0) s u m i = 1 ( s u m r o o t = 0 )

sumi=∑sumson s u m i = ∑ s u m s o n

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N=;
int ch[N<<][],dis[N<<],sum[N<<],fa[N<<],root=,sz=,last=,len;
int c[N],pos[N],size[N<<];
char s[N];

void insert(int x)
{
    int now=++sz,pre=last;
    last=now; size[now]=;
    dis[now]=dis[pre]+;
    for (;pre&&!ch[pre][x];pre=fa[pre]) ch[pre][x]=now;

    if (!pre) fa[now]=root;
    else
    {
        int q=ch[pre][x];
        if (dis[q]==dis[pre]+) fa[now]=q;
        else
        {
            int nows=++sz;
            dis[nows]=dis[pre]+;
            memcpy(ch[nows],ch[q],sizeof(ch[q]));
            fa[nows]=fa[q]; fa[q]=fa[now]=nows;
            for (;pre&&ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
        }
    }
}

void solve(int K)
{
    int now=root;
    while ((K-=size[now])>)
    {
        int x=;
        while (K>sum[ch[now][x]]&&x<) K-=sum[ch[now][x++]];
        printf("%c",'a'+x); 
        now=ch[now][x];
    }
    printf("\n");
}

int main()
{
    scanf("%s",s+); len=strlen(s+);
    for (int i=;i<=len;i++) insert(s[i]-'a');
    int T;
    scanf("%d",&T);

    size[root]=;
    for (int i=;i<=sz;i++) c[dis[i]]++;
    for (int i=;i<=len;i++) c[i]+=c[i-];
    for (int i=;i<=sz;i++) pos[c[dis[i]]--]=i;

    for (int i=sz;i>=;i--)
    {
        sum[pos[i]]=size[pos[i]];
        for (int j=;j<;j++)
            if (ch[pos[i]][j])
                sum[pos[i]]+=sum[ch[pos[i]][j]];
    }

    while (T--)
    {
        int K;
        scanf("%d",&K);
        solve(K);
    }
}