算法：dp+字典树
题目链接Ann and Half-Palindrome
在CF刷字符串题的时候遇到了这题，其实并没有黑题这么难，个人感觉最多是紫题吧（虽然一开始以为是后缀自动机的神仙题）。
首先注意到字符串 \(s\) 长度很小( \(1\le|s|\le5000\) ),可以 \(\mathcal O(n^2)\) 地把所有子串求出来，再用Trie树存起来，这样就方便我们dfs求字典序第 \(k\) 小的半回文串。所以问题重心变为怎么快速判断这些子串是否为半回文串。根据半回文串的特点，长度长的半回文串是包含长度小的半回文串的，所以我们可以用区间dp解决。设 \(f[i][l]\) 表示 \(s[i,i+l-1]\) 是否为半回文串，它的转移方程可以写作( \([A]\) 表示 \(A\) 为真时值为1，否则为0)：
\[\left\{\begin{array}{l}f[i][1]=1\\ f[i][2]=[s[i]=s[i+1]]\\f[i][3]=[s[i]=s[i+2]]\\f[i][4]=[s[i]=s[i+3]] \\ f[i][l]~=[~s[i]=s[i+l-1]\&\&f[i+2][l-4]~],l\ge5\end{array}\right. \]