题目是说给你一个字符串，现在要你用一些特殊的符号代替这个字符串中某一些子串，使得被替换后的串是一个回文串。
现在要你求替换后的字符串的最大的可能的长度。
其实这个题目没有什么固定的算法哦，我直接暴力就过了，但是中间手滑，wa了太多发。
其实可以这样来考虑，我们这个字符串的反序也保存一遍，这样可以建立起一个类似于链表的结构（对于每一个字符，我们在这里指向它下一次出现的下标）
这样如果最后可以被替换为n个串，那么一定存在x1,x2,……,xn，是的1-x1,x1-x2,……xn-1-xn是完美的反向匹配的。
同时我们需要维护每一个x最小，这样就一定是最小的。
虽然可能出现极限数据使得复杂度为n^2，但是……（可能卡到n方吗？）
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100100
using namespace std;
int next[3][maxn][26];
char s[3][maxn];
int n,m,k,t,pos[26],ans,cas=0;
void init_Z(int x)
{
memset(pos,0x3f,sizeof pos);
for (int i=n; i>0; i--)
{
pos[s[x][i]-'A']=i;
for (int j=0; j<26; j++)
next[x][i][j]=pos[j];
}
}
int match(int x)
{
if (x>n/2)
{
if ((n&1) && x==n/2+1) return 1;
else return 0;
}
int pos=max(next[1][x][s[2][x]-'A'],next[2][x][s[1][x]-'A']);
while (1)
{
if (pos>n/2) return 1;
bool flag=true;
for (int i=0; i<pos-x+1; i++)
if (s[1][x+i]!=s[2][pos-i])
{
flag=false;
break;
}
if (flag)
return 2+match(pos+1);
else pos=max(next[1][pos+1][s[2][x]-'A'],next[2][pos+1][s[1][x]-'A']);
}
}
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%s",s[1]+1);
n=strlen(s[1]+1);
for (int i=1; i<=n; i++) s[2][i]=s[1][n+1-i];
init_Z(1); init_Z(2);
ans=match(1);
printf("Case #%d: %d
",++cas,ans);
}
return 0;
}