Description

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

\(T=0\)则表示不同位置的相同子串算作一个。\(T=1\)则表示不同位置的相同子串算作多个。

Solution

\(SAM\)可以用来维护子串的信息，而相类似的子串会由同一个状态来维护。

当\(T=0\)时，我们发现不需要维护\(Right\)集合的大小，我们不妨直接当它是\(1\)

为了查询答案，我们需要记录一下每个状态后继的大小和。

Code 

//2019.1.26 23:20~00:07 #include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define MN 1000005int c[MN][26],step[MN],val[MN],fa[MN],siz[MN],v[MN],rk[MN];int last,cnt,n;inline void init(){    last=cnt=1;memset(c,0,sizeof c);    register int i;    for(i=1;i
     
      <<1;++i) val[i]=step[i]=fa[i]=0;}void Insert(int x){    int p=last,np=++cnt;step[np]=step[p]+1;val[np]=1;    for(;p&&!c[p][x];p=fa[p]) c[p][x]=np;    if(!p) fa[np]=1;    else     {        int q=c[p][x];        if(step[q]==step[p]+1) fa[np]=q;        else         {            int nq=++cnt;step[nq]=step[p]+1;            memcpy(c[nq],c[q],sizeof c[q]);            fa[nq]=fa[q];fa[np]=fa[q]=nq;            for(;c[p][x]==q;p=fa[p]) c[p][x]=nq;        }        }    last=np;}inline void work(){    register int i;    for(i=1;i<=cnt;++i) ++v[step[i]];    for(i=1;i<=n;++i) v[i]+=v[i-1];    for(i=1;i<=cnt;++i) rk[v[step[i]]--]=i;    for(i=cnt;i;--i) val[fa[rk[i]]]+=val[rk[i]],siz[rk[i]]=val[rk[i]];    val[1]=siz[1]=0;}char s[MN],ans[MN];int len;inline void dfs(int x,int k){    if(k<=val[x]) return;k-=val[x];    register int i;    for(i=0;i<26;++i)        if(k>siz[c[x][i]]) k-=siz[c[x][i]];        else {ans[len++]=i+'a',dfs(c[x][i],k);break;}}int main(){    register int i,j,k,type;    scanf("%s%d%d",s+1,&type,&k);n=strlen(s+1);    init();    for(i=1;i<=n;++i) Insert(s[i]-'a');    work();    if(!type) for(i=2;i<=cnt;++i) val[i]=siz[i]=1;    for(i=cnt;i;--i)for(j=0;j<26;++j)if(c[rk[i]][j])siz[rk[i]]+=siz[c[rk[i]][j]];    if(siz[1]
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！