首页 > 代码库 > SPOJ_SUBLEX
SPOJ_SUBLEX
经典题目:给一个字符串,求字典序第k小的子串是什么。
涉及子串问题,上自动机。
首先我们可以用记忆化搜索的方法,求出到达某一个状态后,能产生多少个新状态。
首先,到达这个状态就不走了,这肯定是一种状态,然后分别考虑后面的26个指针就好了。
不过如果不记忆化肯定是要T的,而且如果用dp好像会有一点问题,因为状态转移不是严格的满足小号点到大号点(nq点啦)。
然后就是赤果果的dfs就可以啦。
对了还有一个有趣的事情,一开始我输出字符的地方T了,后来改变字符串的输出方式,然后就A了。spoj真是奇葩呀。能买个好点服务器吗?
召唤代码君:
#include <iostream>#include <cstdio>#include <cstring>#define maxn 222222using namespace std;int next[maxn][26],pre[maxn],step[maxn],f[maxn];char s[maxn];int N,last,n,k;int p,q,np,nq;void insert(int x,int m){ p=last,np=++N,step[np]=m; while (p!=-1 && next[p][x]==0) next[p][x]=np,p=pre[p]; last=np; if (p==-1) return; q=next[p][x]; if (step[q]==step[p]+1) { pre[np]=q; return; } nq=++N,step[nq]=step[p]+1,pre[nq]=pre[q]; for (int i=0; i<26; i++) next[nq][i]=next[q][i]; pre[np]=pre[q]=nq; for (;p!=-1 && next[p][x]==q; p=pre[p]) next[p][x]=nq;}int get(int x){ if (f[x]!=0) return f[x]; f[x]=1; for (int i=0; i<26; i++) if (next[x][i]) f[x]+=get(next[x][i]); return f[x];}void output(int pos,int num,int L){ num--; if (num==0) { s[L]=‘\0‘; printf("%s\n",s+1); return; } for (int i=0; i<26; i++) { if (next[pos][i]==0) continue; if (f[next[pos][i]]<num) num-=f[next[pos][i]]; else { s[L]=‘a‘+i; output(next[pos][i],num,L+1); return; } }}int main(){ pre[0]=-1; scanf("%s",s); for (int i=0; s[i]; i++) insert(s[i]-‘a‘,i+1); f[0]=get(0); scanf("%d",&n); while (n--) { scanf("%d",&k); output(0,k+1,1); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。