傳送門
$sam$基礎(chǔ)題。
題意簡述：給出一個串，詢問第$k$大的本質(zhì)不同的串。

---

然而這就是弦論的簡化版。
我們把$sam$建出來然后貪心選擇就行了。
代碼：

#include<bits/stdc++.h> #define ri register int using namespace std; const int N=2e5+5; int n,q,K; char s[N]; struct SAM{int last,tot,len[N],link[N],son[N][26],rk[N],cnt[N],sum[N];SAM(){last=tot=1;}inline void expand(int x){int p=last,np=++tot;len[last=np]=len[p]+1;while(p&&!son[p][x])son[p][x]=np,p=link[p];if(!p){link[np]=1;return;}int q=son[p][x],nq;if(len[q]==len[p]+1){link[np]=q;return;}len[nq=++tot]=len[p]+1,memcpy(son[nq],son[q],sizeof(son[q])),link[nq]=link[q],link[q]=link[np]=nq;while(p&&son[p][x]==q)son[p][x]=nq,p=link[p]; }inline void topsort(){for(ri i=1;i<=tot;++i)++cnt[len[i]];for(ri i=1;i<=tot;++i)cnt[i]+=cnt[i-1];for(ri i=tot;i;--i)rk[cnt[len[i]]--]=i,sum[i]=1;for(ri i=tot;i;--i)for(ri j=0;j<26;++j)if(son[rk[i]][j])sum[rk[i]]+=sum[son[rk[i]][j]];}inline void query(){int p=1;while(K>0){for(ri i=0,v;i<26;++i){if(!(v=son[p][i]))continue;if(sum[v]>=K){--K,putchar('a'+i),p=v;break;}else K-=sum[v];}}puts("");} }sam; int main(){scanf("%s",s),n=strlen(s);for(ri i=0;i<n;++i)sam.expand(s[i]-'a');sam.topsort(),scanf("%d",&q);while(q--)scanf("%d",&K),sam.query();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ldxcaicai/p/10367810.html

總結(jié)

以上是生活随笔為你收集整理的2018.12.22 spoj7258 Lexicographical Substring Search（后缀自动机）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。