Manacher算法

1. 优化查找效率，以空间换时间
2. 将原字符串转换成长度一定是奇数的字符串

#include<stdio.h>
#include<string.h>
#define min(a,b) (a > b ? b : a)
#define max(a,b) (a > b ? a : b)

int main()
{
    char str[2501];//原字符串
    char tmp[2501<<1];//转换后的字符串
    int Len[2501<<1];//转化后有效长度
    int i;
    scanf("%s", str);
    int len = strlen(str);
    tmp[0]='@';//字符串开头增加一个特殊字符，防止越界
    for(i=1;i<=2*len;i+=2)
    {
        tmp[i]='#';
        tmp[i+1]=str[i/2];
    }
    tmp[2*len+1]='#';
    tmp[2*len+2]='$';//字符串结尾加一个字符，防止越界
    
    int mx=0,ans=0,po=0;//mx即为当前计算回文串最右边字符的最大值
    for(i=1; i <= len*2+1; i++)
    {
         if(mx > i)
         {
             Len[i]=min(mx-i,Len[2*po-i]);//在Len[j]和mx-i中取个小
         }
         else
         {
             Len[i]=1;//如果i>=mx，要从头开始匹配
         }
         while(tmp[i-Len[i]]==tmp[i+Len[i]])
         {
             Len[i]++;
         }
         if(Len[i]+i>mx)//若新计算的回文串右端点位置大于mx，要更新po和mx的值
         {
             mx=Len[i]+i;
             po=i;
         }
         ans=max(ans,Len[i]);
     }
    printf("%d", ans-1);
    return 0;
}