題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的字符串，再給出 $m$ 次詢問，每次詢問需要輸出本質不同第 $k$ 小的子串的起止位置。如果有多個答案，輸出起點最小的那個。強制在線。

題目分析：后綴樹的模板題，在后綴樹上按照字典序前序遍歷維護一下前綴和（子串個數），然后對于每次詢問就可以二分查找答案在哪個節點了。

具體難點有兩條：

如何在后綴樹上按照字典序遍歷

如何維護每個子串首次出現的位置

對應的解決方案如下：

根據 parent 樹邊的性質將子節點排序

維護 endpos 的極值

那么如何求后綴樹呢？其實只需要將字符串反轉一下，然后扔到后綴自動機里，此時求出的 $parent$ 樹就是后綴樹了。

原理也十分簡單，考慮 $parent$ 樹的葉子節點到根節點的一條路徑，表示的是一個前綴的所有后綴，反轉一下自然就變成了一個后綴的所有前綴，也就是后綴樹了。

因為本題需要記錄相應子串的首次出現位置，所以可以維護一下反串中每個節點的 $endpos$ 的最大值用于答案輸出。

剩下的就是億點點坐標轉換的細節了，大家可以用樣例以及：

abcd
1
0
ans=1 1

這組樣例自己調一下，都能調過去的話應該就沒有問題了。

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; char s[N]; vector<int>node[N<<1]; int tot,last,endpos[N<<1]; LL sum[N<<1]; int rk[N<<1],dfn; struct Node {int ch[26];int fa,len; }st[N<<1]; inline int newnode() {tot++;for(int i=0;i<26;i++)st[tot].ch[i]=0;st[tot].fa=st[tot].len=0;endpos[tot]=0;node[tot].clear();return tot; } void add(int x) {int p=last,np=last=newnode();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=newnode();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}} } void dfs_pos(int u) {for(auto v:node[u]) {dfs_pos(v);endpos[u]=max(endpos[u],endpos[v]);} } void dfs(int u,int fa) {if(u!=1) {dfn++;sum[dfn]=sum[dfn-1]+(st[u].len-st[fa].len);rk[dfn]=u;}vector<pair<char,int>>son;for(auto v:node[u]) {son.push_back({s[endpos[v]-st[u].len],v});}sort(son.begin(),son.end());for(auto it:son) {dfs(it.second,u);} } void build() {for(int i=1;i<=tot;i++) {node[st[i].fa].push_back(i);}dfs_pos(1);dfs(1,-1); } void init() {last=1;dfn=tot=0;newnode(); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);while(scanf("%s",s+1)!=EOF) {init();int n=strlen(s+1);reverse(s+1,s+1+n);for(int i=1;i<=n;i++) {add(s[i]-'a');endpos[last]=i;}build();int m;scanf("%d",&m);LL l=0,r=0;while(m--) {LL k;scanf("%lld",&k);k=(k^l^r)+1;if(k<=sum[dfn]) {int t=lower_bound(sum+1,sum+1+dfn,k)-sum;int u=rk[t];int len=st[u].len-(sum[t]-k);l=n-endpos[u]+1;r=l+len-1;} else {l=r=0;}printf("%lld %lld\n",l,r);}}return 0; }

總結

以上是生活随笔為你收集整理的HDU - 5008 Boring String Problem(后缀树求本质不同第k大子串)的全部內容，希望文章能夠幫你解決所遇到的問題。

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