manacher算法

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 const int maxn=110010;
 8 char str[maxn];//原字符串
 9 char tmp[maxn<<1];//转换后的字符串
10 int Len[maxn<<1];
11 //转换原始串
12 int INIT(char *st)
13 {
14     int i,len=strlen(st);
15     tmp[0]=‘@‘;//字符串开头增加一个特殊字符，防止越界
16     for(i=1;i<=2*len;i+=2)
17     {
18         tmp[i]=‘#‘;
19         tmp[i+1]=st[i/2];
20     }
21     tmp[2*len+1]=‘#‘;
22     tmp[2*len+2]=‘$‘;//字符串结尾加一个字符，防止越界
23     tmp[2*len+3]=0;
24     return 2*len+1;//返回转换字符串的长度
25 }
26 //Manacher算法计算过程
27 int MANACHER(char *st,int len)
28 {
29      int mx=0,ans=0,po=0;//mx即为当前计算回文串最右边字符的最大值
30      for(int i=1;i<=len;i++)
31      {
32          if(mx>i)
33          Len[i]=min(mx-i,Len[2*po-i]);//在Len[j]和mx-i中取个小
34          else
35          Len[i]=1;//如果i>=mx，要从头开始匹配
36          while(st[i-Len[i]]==st[i+Len[i]])
37          Len[i]++;
38          if(Len[i]+i>mx)//若新计算的回文串右端点位置大于mx，要更新po和mx的值
39          {
40              mx=Len[i]+i;
41              po=i;
42          }
43          ans=max(ans,Len[i]);
44      }
45      return ans-1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度 
46   }
47 int main()
48 {
49     while(~scanf("%s",str))
50     {
51         int len=INIT(str);
52         int ans=MANACHER(tmp,len);
53         printf("%d\n",ans);
54     }
55     return 0;
56 }

if (i < mx)      p[i] = min(p[2 * id - i], mx - i);