題目鏈接：點擊查看

題目大意：給出一個字符串 s ，再給出 m 次詢問，每次詢問需要回答字符串中第 k 小的的子串(去重后)

題目分析：可以先對字符串 s 構造SAM，因為是去重后的子串，正好對應了SAM上的每個節(jié)點，所以我們可以在SAM上dfs統(tǒng)計每條路下面都還有多少條路可以走，以此作為每次查詢時dfs的依據(jù)，之后按照字典序的狀態(tài)遍歷就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;char s[N];int tot=1,last=1,cnt[N<<1];struct Node {int ch[26];int fa,len; }st[N<<1];void add(int x) {int p=last,np=last=++tot;st[np].len=st[p].len+1;while(p&&!st[p].ch[x])st[p].ch[x]=np,p=st[p].fa;if(!p)st[np].fa=1;else{int q=st[p].ch[x];if(st[p].len+1==st[q].len)st[np].fa=q;else{int nq=++tot;st[nq]=st[q]; st[nq].len=st[p].len+1;st[q].fa=st[np].fa=nq;while(p&&st[p].ch[x]==q)st[p].ch[x]=nq,p=st[p].fa;//向上把所有q都替換成nq}} }int dfs(int u) {if(cnt[u])return cnt[u];cnt[u]=1;for(int i=0;i<26;i++){int v=st[u].ch[i];if(v){dfs(v);cnt[u]+=cnt[v];}}return cnt[u]; }void solve(int cur,int k,int len) {k--;if(k==0){s[len]=0;puts(s);return;}for(int i=0;i<26;i++){int to=st[cur].ch[i];if(!to)continue;if(cnt[to]<k)k-=cnt[to];else{s[len]='a'+i;solve(to,k,len+1);return;}} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%s",s);int len=strlen(s);for(int i=0;i<len;i++)add(s[i]-'a');dfs(1);int m;scanf("%d",&m);while(m--){int k;scanf("%d",&k);solve(1,k+1,0);}return 0; }

?

總結

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

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