Description：

一个空串，每次在开头或末尾加一个字符或者在开头或末尾加一个该串的逆串，求最小化操作数构造给定串 $S$ 。

$1\leqslant n\leqslant 1000$

Solution：

在回文自动机上 $DP$ ，设 $f[i]$ 表示构成 $i$ 这个点代表的回文串的最小操作数， $ans=\min(f[i]+n-len[i])$ 。

考虑 $f[i]$ 的转移，如果 $i$ 是一个偶回文串的话，那么他一定是通过翻转构成的，证明如下：

考虑他上一次的回文串，如果只在回文的一边，那么显然翻转一下更优，否则的话回文串经过中心，肯定有一个关于中心对称的更大的回文串，因此也不优。

所以转移有两种，一是如果把一个串往两边扩展一个能构成当前回文串的话， $d[i]=d[j]+1$ ，二是从一个长度不大于 $n/2$ 的回文后缀转移过来，证明和上面也类似，求这个串可以在上一个串的基础上扩展，这样复杂度就是对的了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

char c[MAXN];

int l;

struct node

{

	int tr[5];

	int len,fail;

}s[MAXN];

int ptr,last;

int f[MAXN];

int trans[MAXN];

int newnode(int l)

{

	memset(&s[ptr],0,sizeof(s[ptr]));

	trans[ptr] = f[ptr] = 0;

	s[ptr].len = l;

	return ptr++;

}

void init()

{

	ptr = last = 0;

	newnode(0);newnode(-1);

	s[0].fail = 1;

	return;

}

int getfail(int i,int p)

{

	while(c[i - s[p].len - 1] != c[i])p = s[p].fail;

	return p;

}

void extend(int i,int k)

{

	int p = getfail(i,last);

	if(s[p].tr[k] == 0)

	{

		int np = newnode(s[p].len + 2);

		s[np].fail = s[getfail(i,s[p].fail)].tr[k];

		s[p].tr[k] = np;

		if(s[np].len <= 2)trans[np] = s[np].fail;

		else

		{

			int q = trans[p];

			while(c[i - s[q].len - 1] != c[i] || (s[q].len + 2) * 2 > s[np].len)q = s[q].fail;

			trans[np] = s[q].tr[k];

		}

	}

	last = s[p].tr[k];

	return;

}

int main()

{

	scanf("%d",&n);

	for(int k = 1;k <= n;++k)

	{

		scanf("%s",c + 1);

		l = strlen(c + 1);

		for(int i = 1;i <= l;++i)

		{

			if(c[i] == 'A')c[i] = 1;

			if(c[i] == 'G')c[i] = 2;

			if(c[i] == 'C')c[i] = 3;

			if(c[i] == 'T')c[i] = 4;

		}

		init();

		for(int i = 1;i <= l;++i)extend(i,c[i]);

		for(int i = 2;i <= ptr;++i)f[i] = s[i].len;

		f[0] = 1;

		int ans = 0x3f3f3f3f;

		for(int i = 0;i <= ptr;++i)

		{

			for(int k = 1;k <= 4;++k)

			{

				if(s[i].tr[k] == 0)continue;

				int x = s[i].tr[k],y = trans[x];

				if(s[x].len % 2 == 0)

				{

					f[x] = f[i] + 1;

					f[x] = min(f[x],s[x].len / 2 - s[y].len + 1 + f[y]);

				}

			}

			ans = min(ans,l - s[i].len + f[i]);

		}

		cout << ans << endl;

	}

	return 0;

}