51Nod 1464 半回文

Problem

一个字符串t是半回文的条件是，对于所有的奇数𝑖(1≤𝑖≤|𝑡|+12)，𝑡𝑖 = 𝑡|𝑡| − 𝑖 + 1 始终成立，|t|表示字符串t的长度。下标从1开始。例如"abaa", "a", "bb", "abbbaa"都是半回文，而"ab", "bba"和"aaabaa"则不是。

现在有一个字符串s，只由小写字母a,b构成，还有一个数字k。现在要求找出s的半回文子串中字典序排在第k位的串，字符串可以是一样，只要所在的位置不同就是不一样的串。

样例解释：

这个样例中半回文子串是 a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab,bab, bb, bbab, bbabaab (按照字典序排序).

Solution

dp预处理出i到j是不是半回文，然后字典树上遍历。

Code

#include<stdio.h>
#include<set>
#include<iostream>
#include<stack>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod=1e9+7;
inline int mo(ll a,int p){
    return a>=p?a%p:a;
}
inline int rd() {
    int x = 0, f = 1;
    char ch;
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f * x;
}
inline ll gcd(ll x, ll y){
    return y==0?x:gcd(y,x%y);
}
inline ll speed(ll a,ll b,int p){
    ll cur=a,anss=1;
    while(b){
        if(b&1) anss=anss*cur%p;
        cur=cur*cur%p;
        b>>=1;
    }
    return anss%p;
}
const int MAXN=1e5;
bool ipr[MAXN+20];
/*int cnt,pri[MAXN/5];
void prime(){//埃式筛法
    int N=sqrt(MAXN)+0.5,mul;
    memset(ipr,true,sizeof(ipr));
    ipr[1]=false;
    for(int i=2;i<=N;i++){
        if(ipr[i]==true){
            i==2?mul=1:mul=2;
            for(int j=i*i;j<=MAXN;j+=i*mul){
                ipr[j]=false;
            }
        }
    }
    for(int i=2;i<=MAXN;i++){
        if(ipr[i]==true){
            pri[++cnt]=i;
        }
    }
}*/
int k,len,cnt;
char s[5020];
struct E{
    int d,t;
    int nex[2];
}e[5500020];
int dp[5020][5020];
int vis[5020];
int ct=0,ansn;
bool fg=false;
char ans[5020];
void dfs(int cur,int layer){
    if(fg) return;
    if(layer!=0){
        ans[layer]=e[cur].d+'a';
    }
    ct+=e[cur].t;
    if(ct>=k){
        fg=true;
        ansn=layer;
        return;
    }
    for(int i=0;i<=1;i++){
        if(e[cur].nex[i]){
            dfs(e[cur].nex[i],layer+1);
        }
    }
}
int main(){
    //io_opt;
    scanf("%s",s);
    scanf("%d",&k);
    len=strlen(s);
    for(int i=len-1;i>=0;i--){
        dp[i][i]=1;
        vis[i]=i;
        for(int j=i+1;j<len;j++){
            if(s[i]==s[j]){
                if(i+2>=j-2){
                    dp[i][j]=1;
                }
                else{
                    dp[i][j]=dp[i+2][j-2];
                }
            }
            if(dp[i][j]) vis[i]=j;
        }
    }
    int cur;
    for(int i=0;i<len;i++){
        cur=0;
        for(int j=i;j<=vis[i];j++){
            int c=s[j]-'a';
            if(!e[cur].nex[c]){
                e[cur].nex[c]=++cnt;
            }
            cur=e[cur].nex[c];
            e[cur].d=c;
            if(dp[i][j]) e[cur].t++;
        }
    }
    dfs(0,0);
    for(int i=1;i<=ansn;i++){
        printf("%c",ans[i]);
    }
    return 0;
}