【bzoj3998】[TJOI2015]弦论

2015.06.17 09:08 Wed | 24次阅读 | 旧日oi | 固定链接 | 源码

Description

对于一个给定长度为N的字符串,求它的第K小子串是什么。

题解

弦论是什么鬼……
后缀自动机裸题嘛~虽然我还是调了好久……
把串建立后缀自动机,T=0时把每个节点的cnt设为1,否则扫一遍设为出现的次数,每个点的num代表以这个点代表的串为开头的串有多少(不包含这个点本身),然后两种情况就可以一起处理了。简单的循环一遍就行了。
其实不判-1也能过……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000005
#define ll long long
using namespace std;
char s[N];
int T,K,len;
struct SAM
{
    int son[N][26],fa[N],len[N],v[N],rk[N];
    ll cnt[N],num[N];
    int tot,last;
    void init()
    {
        last=tot=1;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot;len[nq]=len[p]+1;
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                memcpy(son[nq],son[q],sizeof(son[nq]));
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        }
    }
    int ans[N],top;
    void solve(int L)
    {
        for(int i=1;i<=tot;i++) v[len[i]]++;
        for(int i=1;i<=L;i++) v[i]+=v[i-1];
        for(int i=tot;i;i--) rk[v[len[i]]--]=i;
        if(T==0) for(int i=2;i<=tot;i++) cnt[i]=1;
        else
        {
            for(int now,p=1,i=0;i<L;i++)
            {
                now=s[i]-'a';
                cnt[p=son[p][now]]=1;
            }
            for(int i=tot;i>1;i--) 
            cnt[fa[rk[i]]]+=cnt[rk[i]];
        }
        for(int k,i=tot;i;i--)
        {
            k=rk[i];
            for(int j=0;j<26;j++)
            if(son[k][j]) num[k]+=num[son[k][j]]+cnt[son[k][j]];
        }
        int p=1;
        while(K>0)
        {
            for(int j=0;j<26;j++)
            if(son[p][j])
            {
                if(num[son[p][j]]+cnt[son[p][j]]<K) 
                    K-=num[son[p][j]]+cnt[son[p][j]];
                else 
                {
                    ans[++top]=j;
                    p=son[p][j];K-=cnt[p];
                    break;
                }
            }
        }
        for(int i=1;i<=top;i++) printf("%c",ans[i]+'a');
        puts("");
    }
}sam;
int main()
{
    scanf("%s",s);len=strlen(s);
    cin>>T>>K;
    sam.init();
    for(int i=0;i<len;i++) sam.insert(s[i]-'a');
    sam.solve(len);
}```