傳送門[洛谷]

心態崩了我有妹子

靠 我寫的記憶化搜索 莫名WA了 然后心態崩了

當我正要改成bfs排序的時候 我靈光一動 md我寫的i=0;i<25;i++？？？

然后 改過來就A掉了T^T

大體做法就是 一個點出發的本質不同子串數量應該是就是所有添加字符的轉移和其余選一個空串的轉移

所以直接建出自動機然后 我的做法是直接記憶化搜索就可以省去建樹/排序 因為所有子串必定由轉移構成 所以可以直接記憶化

附代碼。（我覺得這個做法巨強無比）

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define inf 20021225 #define ll long long #define mxn 90010 using namespace std;struct node{int ch[26],fa,len,f;}t[mxn*4]; int poi,cnt,lt,rt;char ch[mxn]; int id(char c){return c-'a';} void insert(int c) {int p=lt,np=lt=++poi; t[np].len=t[p].len+1;for(;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=np;if(!p){t[np].fa=rt;return;}int q=t[p].ch[c];if(t[q].len==t[p].len+1){t[np].fa=q;return;}int nq=++poi; t[nq].len=t[p].len+1;memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch));t[nq].fa=t[q].fa; t[q].fa=t[np].fa=nq;for(;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=nq; } int query(int x) {if(~t[x].f) return t[x].f;t[x].f=1;for(int i=0;i<26;i++)if(t[x].ch[i])t[x].f+=query(t[x].ch[i]);return t[x].f; } int n; void getans(int pos,int k) {if(!k) return;for(int i=0;i<26;i++)if(t[pos].ch[i]){if(t[t[pos].ch[i]].f<k) k-=t[t[pos].ch[i]].f;else{ch[++n]=i+'a';getans(t[pos].ch[i],k-1);break;}} } int main() {scanf("%s",ch+1);n=strlen(ch+1);rt=lt=++poi;for(int i=1;i<=n;i++) insert(id(ch[i]));for(int i=1;i<=poi;i++) t[i].f=-1;query(rt);//for(int i=1;i<=poi;i++) printf("%d\n",t[i].f);int T;scanf("%d",&T);while(T--){for(int i=1;i<=n;i++) ch[i]=0;int k;scanf("%d",&k);n=0;getans(rt,k);for(int i=1;i<=n;i++) printf("%c",ch[i]);printf("\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的SPOJ7258 SUBLEX - Lexicographical Substring Search的全部內容，希望文章能夠幫你解決所遇到的問題。

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