题意：
若一个字符串是半回文串。则满足第一位和最后一位相等， 第三位和倒数第三位相等。如此类推。
给定一个字符串s，输出s的全部子串中的半回文串字典序第k大的 字符串。
good[i][j] 表示 s(i,j) 是半回文串。
把这些回文串插到字典树里 在字典树上找第k个叶子节点。
插入时：插入以i点开头的全部半回文串。
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ?-1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) pt(x / 10);
putchar(x % 10 + '0');
}
typedef int ll;
typedef pair<int, int> pii;
const int inf = 1e9;
const int N = 5005;
bool good[N][N];
#define Word_Len 5050000
#define Sigma_size 2 struct <span class="KSFIND_CLASS_SELECT" id="0KSFindDIV">Trie</span> {
ll ch[Word_Len][Sigma_size], sz; //Word_Len是字典树的节点数 若都是小写字母Sigma_size=26 sz为当前节点数
ll Have_word[Word_Len]; //这个节点下有几个单词
ll val[Word_Len]; // 这个节点附带的信息，初始化为0表示这个节点不存在单词，所以节点带的信息必须!=0
ll pre[Word_Len];
char he[Word_Len];
ll Newnode() { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = Have_word[sz] = 0; return sz++; }
void init() //初始化字典树
{
sz = 0; Newnode();
}//初始化
ll idx(char c) { return c - 'a'; } //字符串编号 int insert(char *s, int start) { //把v数字加给 s单词最后一个字母
ll u = 0;
for (ll i = 0; s[i]; i++) {
ll c = idx(s[i]);
if (!ch[u][c]) //节点不存在就新建后附加
{
ch[u][c] = Newnode();
he[sz - 1] = s[i];
pre[sz - 1] = u;
}
u = ch[u][c];
if (good[start][start + i]) Have_word[u]++;
}
return u;
}
void dfs(int u) {
val[u] += Have_word[u];
for (int i = 0; i < Sigma_size; i++)
{
int v = ch[u][i];if (!v)continue;
dfs(v);
val[u] += val[v];
}
}
int find_kth(int u, int k) {
if (u)putchar(he[u]);
if (k <= Have_word[u])return u;
k -= Have_word[u];
for (int i = 0; i < Sigma_size; i++)
{
int v = ch[u][i];if (!v)continue;
if (k <= val[v])
{
return find_kth(v, k);
}
else k -= val[v];
}
}
} ac;
int n, k;
char s[N];
int main() {
scanf("%s", s);
rd(k);
n = strlen(s);
for (int i = 0; i < n; i++)
{
for (int l = i, r = i; l >= 0 && r < n; l --, r ++)
{
if (s[l] == s[r])
if (l + 2 >= r - 2 || r - 2 < 0 || l + 2 >= n || good[l + 2][r - 2])
good[l][r] = true;
}
for (int l = i, r = i + 1; l >= 0 && r < n; l --, r ++)
{
if (s[l] == s[r])
if (l + 2 >= r - 2 || r - 2 < 0 || l + 2 >= n || good[l + 2][r - 2])
good[l][r] = true;
}
}ac.init();
for (int i = 0; i < n; i++)
{
int j = n - 1;
while (good[i][j] == false)j--;
char c = s[j + 1]; s[j + 1] = 0;
ac.insert(s + i, i);
s[j + 1] = c;
}ac.dfs(0);
ac.val[0] = 0;
ac.find_kth(0, k);
return 0;
}
titriTrie
