题目地址：传送门 先用dp求出所有的符合要求的半回文串，标记出来。然后构造字典树。然后再dfs一遍求出所有节点的子树和，最后搜一遍就能找出第k个来了。 代码如下：
#include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) //#pragma comment(linker, /STACK:1024000000) const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=400000+10; int ok[5001][5001]; int k, cnt; char s[6000], str[6000]; struct node { int flag, sum; node *next[2]; }; node *newnode() { int i; node *p=new node; for(i=0;i<2;i++){ p->next[i]=NULL; } p->flag=0; p->sum=0; return p; } void Insert(int st, int len, node *root) { int i, x; node *p=root; for(i=st;i next[x]==NULL) p->next[x]=newnode(); p=p->next[x]; if(ok[st][i]) { p->flag++; p->sum++; } } } void dfs(node *u) { for(int i=0;i<2;i++){ if(u->next[i]!=NULL){ dfs(u->next[i]); u->sum+=u->next[i]->sum; } } } void seach(node *root) { node *p=root; while(1){ k-=p->flag; if(k<=0){ return ; } if(p->next[0]!=NULL){ if(p->next[0]->sum>=k){ str[cnt]='a'; p=p->next[0]; cnt++; continue ; } else k-=p->next[0]->sum; } str[cnt]='b'; p=p->next[1]; cnt++; } } int main() { int i, j, len, h; while(scanf(%s,s)!=EOF){ scanf(%d,&k); len=strlen(s); memset(ok,0,sizeof(ok)); for(i=0;i
?