\(\text{Problem}\)
\(\text{Solution}\)
最优解一定是一个回文子串的最优构造加上剩下的逐个填入
考虑用回文树建出所有的回文串，然后 \(dp\) 求回文子串最优的构造方案
维护一个 \(\text{half}\) 意义同 \(\text{fail}\)，但要保证长度不超过 \(len\) 的一半且最大
暴力跳 \(\text{fail}\) 发现不行
加上一个小 \(\text{trick}\)：倒着做，用 \(x\) 的 \(\text{half}\) 更新 \(\text{fail[x]}\) 的 \(\text{half}\)
正确性显然
\(\text{Code}\)
#include <cstdio>
#include <cstring>
#include <iostream>
#define re register
using namespace std;
const int N = 1e5 + 5;
int T, Len;
char str[N];
struct PAM{
int size, last, tot, tr[N][26], fail[N], half[N], len[N], f[N], fa[N];
char s[N];
inline int Node(int l)
{
++size, memset(tr[size], 0, sizeof tr[size]);
len[size] = l, fail[size] = half[size] = 0;
return size;
}
inline void clear()
{
size = -1, s[last = tot = 0] = ‘$‘;
Node(0), Node(-1), fail[0] = 1;
memset(f, 0, sizeof f), f[0] = 1;
}
inline int getfail(int x)
{
while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
return x;
}
inline void insert(char c)
{
s[++tot] = c;
int cur = getfail(last), ch = c - ‘a‘;
if (!tr[cur][ch])
{
int u = Node(len[cur] + 2);
fail[u] = tr[getfail(fail[cur])][ch], fa[u] = cur, tr[cur][ch] = u;
}
last = tr[cur][ch];
}
inline void gethalf()
{
for(re int i = 2; i <= size; i++) half[i] = fail[i];
for(re int i = size; i >= 2; i--)
{
while ((len[half[i]] << 1) > len[i]) half[i] = fail[half[i]];
if (len[half[i]] < len[half[fail[i]]]) half[fail[i]] = half[i];
}
}
inline int dp()
{
int ans = Len;
for(re int i = 2; i <= size; i++)
{
if (len[i] & 1) f[i] = min(f[fa[i]] + 2, f[fail[i]] + len[i] - len[fail[i]]);
else f[i] = min(f[fa[i]] + 1, f[half[i]] + (len[i] >> 1) - len[half[i]] + 1);
ans = min(ans, f[i] + Len - len[i]);
}
return ans;
}
}P;
int main()
{
scanf("%d", &T);
for(; T; --T)
{
P.clear();
scanf("%s", str + 1);
Len = strlen(str + 1);
for(re int i = 1; i <= Len; i++) P.insert(str[i]);
P.gethalf();
printf("%d\n", P.dp());
}
}