题意
给一个字符串, 求最长回文镜像子串长度
思路
【Gym 101350I - Mirrored String II ( Manacher马拉车算法 -- 最长回文子串 )】Manacher + 镜像判断
算法实现 : Manacher算法总结
AC代码 ( kuangbin板子 )
#include
#include
#include
#include
#define mst(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn = 1e3+10;
int len;
char mrk[] = "AHIM OTUVWXY ";
char Ma[maxn*2];
int Mp[maxn*2];
void Manacher( char s[], int len ){
int l = 0;
Ma[l++] = '$';
Ma[l++] = '#';
for( int i = 0;
i < len;
i++ ){
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = 0;
int mx = 0, id = 0;
for( int i = 0;
i < l;
i++ ){
Mp[i] = mx > i ? min(Mp[2*id-i], mx-i) : 1;
while( Ma[i+Mp[i]] == Ma[i-Mp[i]] && mrk[Ma[i+Mp[i]]-'A'] != ' ' && mrk[Ma[i-Mp[i]]-'A'] != ' ' ) Mp[i]++;
if( i+Mp[i] > mx ){
mx = i + Mp[i];
id = i;
}
}
}char s[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--){
mst(s);
mst(Ma);
mst(Mp);
scanf("%s",s);
len = strlen(s);
Manacher(s, len);
int ans = 0;
for( int i = 0;
i < 2*len+2;
i++ )
if( mrk[Ma[i]-'A'] != ' ' )
ans = max(ans, Mp[i]-1);
printf("%d\n",ans);
}
return 0;
}
