[CERC2014]Virus synthesis:
题目大意:
初始有一个空串,利用下面的操作构造给定串 \(S\) 。
1、串开头或末尾加一个字符
2、串开头或末尾加一个该串的逆串
求最小化操作数, \(|S| \leq 10^5\) 。
思路:
回文自动机好题。在求出失配指针时,求出 \(\mathrm{trans}_i\) 表示以 \(i\) 结尾的回文串后半段起始位置。
然后可以在回文树上 DP,设 \(f_i\) 表示变成 \(i\) 串的最小代价。
那么有:
\[\begin{aligned} f_u&\leftarrow f_{\mathrm{trans}_u} + 1 + \frac{\mathrm{len}_u}{2} - \mathrm{len}_{\mathrm{trans}_u}\\ f_u&\leftarrow f_{\mathrm{fa}_u}+1 \end{aligned} \]那么 \(u\) 串的贡献为 \(n+f_u-\mathrm{len}_u\)
代码:
const int N = 1e5 + 10;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int t;
char s[N];
int Code(char c)
{
switch (c)
{
case 'A': return 1;
case 'G': return 2;
case 'C': return 3;
case 'T': return 4;
}
}
AK PAM
{
int s[N], len[N], trans[N], fail[N], t[N][26];
int tot, lst, n;
int f[N], ans;
int New(int x)
{
len[++tot] = x;
return tot;
}
void Build()
{
for (int i = 0; i <= tot; i++)
for (int j = 1; j <= 4; j++)
t[i][j] = 0;
tot = -1, n = 0;
New(0), New(-1);
s[0] = -1, fail[0] = 1;
}
int Find(int x)
{
while (s[n - 1 - len[x]] != s[n]) x = fail[x];
return x;
}
void Insert(int x)
{
s[++n] = x;
int cur = Find(lst);
if (!t[cur][x])
{
int now = New(len[cur] + 2),
tmp = Find(fail[cur]);
fail[now] = t[tmp][x];
t[cur][x] = now;
if (len[now] <= 2) trans[now] = fail[now];
else
{
tmp = trans[cur];
while (s[n - 1 - len[tmp]] != s[n] || (len[tmp] + 2 << 1) > len[now]) tmp = fail[tmp];
trans[now] = t[tmp][x];
}
}
lst = t[cur][x];
}
void Solve(int n)
{
queue<int> q;
for (int i = 1; i <= 4; i++)
if (t[0][i]) q.push(t[0][i]);
for (int i = 2; i <= tot; i++) f[i] = len[i];
while (!q.empty())
{
int u = q.front(); q.pop();
f[u] = min(f[u], f[trans[u]] + 1 + len[u] / 2 - len[trans[u]]);
ans = min(ans, n - len[u] + f[u]);
for (int i = 1; i <= 4; i++)
if (t[u][i])
{
int v = t[u][i];
f[v] = min(f[v], f[u] + 1);
q.push(v);
}
}
}
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
for (t = Read(); t--; )
{
scanf ("%s", s + 1);
PAM::Build();
int len = strlen(s + 1);
for (int i = 1; i <= len; i++)
PAM::Insert(Code(s[i]));
PAM::ans = len;
PAM::Solve(len);
printf ("%d\n", PAM::ans);
}
return 0;
}