题目描述

难度分: $2300$

输入长度$\leq 5000$的字符串$s$，只包含a和b。

设$t$是$s$的一个连续子串，长为$m$，下标从$1$开始。如果对于$[1,\lceil \frac{m}{2} \rceil]$中的所有奇数下标$i$，都满足$t[i]=t[m-i+1]$，那么称$t$为半回文串。

然后输入正整数$k$。

输出$s$的字典序第$k$小的半回文子串。保证$k$不超过$s$的半回文子串的个数。

输入样例$1$

abbabaab
7

输出样例$1$

abaa

输入样例$2$

aaaaa
10

输出样例$2$

aaa

输入样例$3$

bbaabb
13

输出样例$3$

bbaabb

算法

一周灵茶$AK$时刻！

动态规划+字典树

首先我们要知道哪些子串$[l,r]$是半回文的，然后确定字典序排名第$k$的是哪个。

状态定义

$f[l][r]$表示子串$[l,r]$是否是半回文串。

状态转移

按照区间DP的套路，外层循环遍历长度$len \in [2,n]$（初始化$f[i][i]=$true，$i \in [1,n]$）。内层循环遍历右端点$r \in [len,n]$，那么左端点为$l=r-len+1$。接下来状态转移在$s[l]=s[r]$成立时有两种情况：

1. $len$是奇数，当$len=3$时$f[l][r]=$true；当$len \gt 3$时，$[l,r]$是否半回文取决于$[l+2,r-2]$是否为半回文，状态转移方程为$f[l][r]=f[l+2][r-2]$。
2. $len$是偶数，当$len \leq 4$时$f[l][r]=$true；当$len \gt 4$时，$[l,r]$是否半回文取决于$[l+2,r-2]$是否为半回文，状态转移方程为$f[l][r]=f[l+2][r-2]$。

构建一个映射$l2r$，当$l$是半回文串的起始字符时，$l2r[l]$是这些半回文串的右端点列表（按照升序排列）。然后遍历$l \in [1,n]$，按照增量的方式把$[l,r_i]$插入到字典序中，即先插入$[l,r_1]$，然后插入$[r_1+1,r_2]$，……，依次类推，反正只有每个右端点才打单词结尾标记，这样插是没问题的。否则每次都插入$[l,r_i]$的话，子串数量是$O(n^2)$，插入字典树的时间复杂度为$O(n)$，就会得到一个$O(n^3)$的操作从而超时。

DFS遍历字典树

从字典树的根节点开始DFS，每层节点都先遍历a再遍历b，这样就能保证是按照最小字典序在遍历。每遇到一个半回文结尾位置的节点，排名就增加，直到排名覆盖住$k$，这样就能够构造出排名第$k$的半回文串，详见代码。

复杂度分析

时间复杂度

区间DP的时间复杂度为$O(n^2)$；预处理出$l2r$需要双重循环遍历$s$的所有子串，时间复杂度也为$O(n^2)$；接下来将$O(n^2)$级别的本回文串加入到字典树中，对于$O(n)$个$l$，都需要遍历$O(n)$级别的右端点，时间复杂度为$O(n)$，总的时间复杂度为$O(n^2)$；最后对字典树进行深度优先遍历，字典树的节点个数为$O(n^2\Sigma)$，本题$s$串只包含a和b两种字符，因此字符集大小$\Sigma=2$，时间复杂度为$O(n^2)$。

综上，整个算法的时间复杂度为$O(n^2)$。

空间复杂度

DP矩阵$f$、映射$l2r$，以及字典树的空间复杂度均为$O(n^2)$，所以整个算法的额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 5001;
int n, k, rk;
char s[N];
bool f[N][N];
vector<int> l2r[N];
string ans;

class TrieNode {
public:
    int end;
    TrieNode* next[2];
    TrieNode() {
        end = 0;
        for(int i = 0; i < 2; i++) {
            next[i] = nullptr;
        }
    }
};

TrieNode* root;

void insert(int l, int r, int d) {
    TrieNode* cur = root;
    for(int i = l; i <= r; i++) {
        int idx = s[i] - 'a';
        if(cur->next[idx] == nullptr) {
            cur->next[idx] = new TrieNode;
        }
        cur = cur->next[idx];
    }
    cur->end += d;
}

bool dfs(TrieNode* node) {
    if(node->end > 0) {
        k -= node->end;
        if(k <= 0) return true;
    }
    for(int i = 0; i < 2; i++) {
        if(node->next[i]) {
            ans.push_back('a' + i);
            if(dfs(node->next[i])) {
                return true;
            }
            ans.pop_back();
        }
    }
    return false;
}

int main() {
    scanf("%s", s + 1);
    scanf("%d", &k);
    n = strlen(s + 1);
    memset(f, 0, sizeof f);
    for(int i = 1; i <= n; i++) {
        f[i][i] = true;
    }
    for(int len = 2; len <= n; len++) {
        for(int r = len; r <= n; r++) {
            int l = r - len + 1;
            if(len&1) {
                if(s[l] == s[r]) {
                    if(len == 3) {
                        f[l][r] = true;
                    }else {
                        f[l][r] = f[l + 2][r - 2];
                    }
                }
            }else {
                if(s[l] == s[r]) {
                    if(len <= 4) {
                        f[l][r] = true;
                    }else {
                        f[l][r] = f[l + 2][r - 2];
                    }
                }
            }
        }
    }
    for(int l = 1; l <= n; l++) {
        l2r[l].clear();
        for(int r = l; r <= n; r++) {
            if(f[l][r]) {
                // [l,r]是半回文串，插入到字典树中
                l2r[l].push_back(r);
            }
        }
    }
    root = new TrieNode;
    for(int l = 1; l <= n; l++) {
        TrieNode* cur = root;
        int pre = l, d = l2r[l].size();
        for(int r: l2r[l]) {
            for(int i = pre; i <= r; i++) {
                int idx = s[i] - 'a';
                if(cur->next[idx] == nullptr) {
                    cur->next[idx] = new TrieNode;
                }
                cur = cur->next[idx];
            }
            cur->end++;
            pre = r + 1;
        }
    }
    ans.clear();
    dfs(root);
    cout << ans << endl;
    return 0;
}