SUBLEX - Lexicographical Substring Search - 洛谷

題意

給定一個字符串，求本質不同排名第k小的子串

輸入格式：

第一行給定主串(len<=90000)

第二行給定詢問個數T<=500

隨后給出T行T個詢問，每次詢問排名第k小的串，范圍在int內

輸出格式：

對于每一個詢問，輸出T行，每行為排名第k小的串

題解：

后綴自動機比較板的一道題，問字串第k小，我們用自動機本身的a-z字典序挨個判斷，如果在里面就進去再判斷。預處理沒見過，我太菜了

void tops(){for(int i=1;i<=cnt;i++) a[tre[i].len]++;for(int i=1;i<=cnt;i++) a[i]+=a[i-1];for(int i=1;i<=cnt;i++) id[a[tre[i].len]--]=i;for(int i=cnt;i>=1;i--){sz[id[i]]=1;for(int j=0;j<26;j++){int v=tre[id[i]].ch[j];if(!v)continue;sz[id[i]]+=sz[v];}} }

然后就是說過的第k小：

void query(int k){int x=1;while (k){for (int i=0;i<26;i++){if (tre[x].ch[i]){if (sz[tre[x].ch[i]]>=k){putchar('a'+i);x=tre[x].ch[i];k--;break;}else k-=sz[tre[x].ch[i]];}}}puts(""); }

感覺還是比較好理解的。

參考代碼：

/*keep on going and never give up*/ #include<bits/stdc++.h> using namespace std; #define int long long #define ll long long #define db(x) cerr<<(#x)<<" "<<(x)<<" "<<endl; #define endl "\n" #define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int maxn=2e6+10; struct node{int ch[26];int len,fa;node(){memset(ch,0,sizeof(ch));len=fa=0;} }tre[maxn];int cnt=1,las=1; void ex_sam(int c){int p=las,np=las=++cnt;tre[np].len=tre[p].len+1;for(;p&&!tre[p].ch[c];p=tre[p].fa)tre[p].ch[c]=np;if(p==0)tre[np].fa=1; else{int q=tre[p].ch[c];if(tre[q].len==tre[p].len+1)tre[np].fa=q; else{int nq=++cnt;tre[nq]=tre[q];tre[nq].len=tre[p].len+1;tre[q].fa=tre[np].fa=nq;for(;p&&tre[p].ch[c]==q;p=tre[p].fa)tre[p].ch[c]=nq;}} } int a[maxn],id[maxn],sz[maxn]; void tops(){for(int i=1;i<=cnt;i++) a[tre[i].len]++;for(int i=1;i<=cnt;i++) a[i]+=a[i-1];for(int i=1;i<=cnt;i++) id[a[tre[i].len]--]=i;for(int i=cnt;i>=1;i--){sz[id[i]]=1;for(int j=0;j<26;j++){int v=tre[id[i]].ch[j];if(!v)continue;sz[id[i]]+=sz[v];}} } void query(int k){int x=1;while (k){for (int i=0;i<26;i++){if (tre[x].ch[i]){if (sz[tre[x].ch[i]]>=k){putchar('a'+i);x=tre[x].ch[i];k--;break;}else k-=sz[tre[x].ch[i]];}}}puts(""); } string s; signed main(){cin>>s;for(auto c:s) ex_sam(c-'a');tops();int q;cin>>q;while(q--){int k;cin>>k;query(k);} }

總結

以上是生活随笔為你收集整理的SP7258 SUBLEX （后缀自动机）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。