題目鏈接
鏈接是洛谷有翻譯的鏈接。

題意：
給你一個(gè)字符串，有T次詢問(wèn)，每次問(wèn)你在整個(gè)字符串中排名為k的子串是哪一個(gè)。字符串長(zhǎng)度<=90000，T<=500，只統(tǒng)計(jì)本質(zhì)不同的串。

題解：
后綴自動(dòng)機(jī)題，因?yàn)楹缶Y自動(dòng)機(jī)有著很強(qiáng)的處理子串的能力。

看到排名第k，我們可能會(huì)想到主席樹(shù)，但是顯然主席樹(shù)是沒(méi)法維護(hù)具體某個(gè)字符串，但是主席樹(shù)查詢第k大的思想我們是可以使用的。主席樹(shù)的方法是看左子樹(shù)的size是否比k大，然后來(lái)確定進(jìn)入左子樹(shù)還是把k減去左子樹(shù)的size進(jìn)入右子樹(shù)。

其實(shí)在后綴自動(dòng)機(jī)是我們也是可以用到這個(gè)思想的。我們先建出給出字符串的后綴自動(dòng)機(jī)，然后我們其實(shí)可以發(fā)現(xiàn)，后綴自動(dòng)機(jī)上的所有轉(zhuǎn)移邊構(gòu)成了一個(gè)DAG（也是后綴自動(dòng)機(jī)的性質(zhì)），那么對(duì)于DAG，我們是可以拓?fù)渑判虻摹＿@里可以用一種比較特殊的拓?fù)渑判?#xff0c;這種寫(xiě)法有點(diǎn)類似與基數(shù)排序，我們把長(zhǎng)的串排在短的串后面，后建的節(jié)點(diǎn)排在先建的節(jié)點(diǎn)后面，這樣一定是一種合法的拓?fù)湫颉Ｈ缓笪覀兏鶕?jù)這個(gè)拓?fù)湫?#xff0c;我們用反著的拓?fù)湫?#xff0c;求出SAM上每個(gè)點(diǎn)能到達(dá)的所有點(diǎn)的個(gè)數(shù)，也就是原串中它的后綴個(gè)數(shù)每個(gè)點(diǎn)本身的size都是1，因?yàn)閺钠瘘c(diǎn)到每個(gè)點(diǎn)都會(huì)形成一個(gè)子串。這樣我們可以像在主席樹(shù)上一樣，從根開(kāi)始走，從小的字母往大的字母嘗試走，看走到哪個(gè)字母正好超過(guò)當(dāng)前k，如果當(dāng)前枚舉到的出邊到達(dá)的點(diǎn)的size比k小，我們就減去這個(gè)size；如果比k大了，就不再減size，轉(zhuǎn)而輸出那個(gè)字母，然后走過(guò)去。這樣說(shuō)可能不是很容易說(shuō)明白，具體可以看看代碼。

代碼

#include <bits/stdc++.h> using namespace std;int T,n,len[400010],fa[400010],cnt=1,rt=1,lst=1,ch[400010][26]; int sz[400010],a[400010],rk[400010],m; char s[100010]; inline void insert(int x) {int cur=++cnt,pre=lst;lst=cur;len[cur]=len[pre]+1;for(;pre&&!ch[pre][x];pre=fa[pre])ch[pre][x]=cur;if(!pre)fa[cur]=rt;else{int ji=ch[pre][x];if(len[ji]==len[pre]+1)fa[cur]=ji;else{int gg=++cnt;len[gg]=len[pre]+1;memcpy(ch[gg],ch[ji],sizeof(ch[ji]));fa[gg]=fa[ji];fa[ji]=fa[cur]=gg;for(;pre&&ch[pre][x]==ji;pre=fa[pre])ch[pre][x]=gg;}} } inline void query(int x) {int ji=rt;while(x){if(ji!=rt)--x;if(x<=0)break;for(int i=0;i<=25;++i){if(sz[ch[ji][i]]<x)x-=sz[ch[ji][i]];else{printf("%c",'a'+i);ji=ch[ji][i];break;}}}printf("\n"); } int main() {scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;++i)insert(s[i]-'a');for(int i=cnt;i>=1;--i)a[len[i]]++;for(int i=1;i<=n;++i)a[i]+=a[i-1];for(int i=cnt;i>=1;--i)rk[a[len[i]]--]=i;for(int i=1;i<=cnt;++i)sz[i]=1;for(int i=cnt;i>=1;--i){for(int j=0;j<=25;++j)sz[rk[i]]+=sz[ch[rk[i]][j]];}scanf("%d",&T);while(T--){scanf("%d",&m);query(m);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的SPOJ7258 SUBLEX 后缀自动机的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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