题意

给一个字符串, 求最长回文镜像子串长度

思路

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[] = "A      HI   M O    TUVWXY ";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;}