SPOJ7258 SUBLEX - Lexicographical Substring Search

传送门[洛谷]

心态崩了我有妹子

靠 我写的记忆化搜索 莫名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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。