hdu3294 Manacher算法模板

题目链接：http://icpc.njust.edu.cn/Problem/Hdu/3294/

回文长度如果是mxx,回文中心是id的话，在扩展串中(id-mxx+1,id+mxx-1)的这段中去除标记符号的部分就是回文串。还有个注意点就是错位循环赋值的问题。

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a,b) memset(a,b,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define pi 3.14159265

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define inf 0x3f3f3f3f

 #define maxn 200010

 int n,m,t;

 char s[maxn],ma[maxn<<];

 int Len[maxn<<];

 int mxx,id;//最大回文半径和中心

 void init(char c,char* s)

 {

     int len=strlen(s);

     f(i,,len-)

     {

         s[i]=(char)('a'+(s[i]-c+)%);

     }

 }

 void manacher(char* s,int len)

 {

     int l=;

     ma[l++]='$';

     ma[l++]='#';

     f(i,,len-)

     {

         ma[l++]=s[i];

         ma[l++]='#';

     }

     ma[l]=;

     int pos=,mr=;

     mxx=;

     f(i,,l-)

     {

         Len[i]=(mr>i)?min(mr-i,Len[*pos-i]):;

         while(ma[i+Len[i]]==ma[i-Len[i]])Len[i]++;

         if(i+Len[i]>mr)mr=i+Len[i],pos=i;

         if(Len[i]->mxx)

         {

             mxx=Len[i]-;

             id=i;

         }

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     std::ios::sync_with_stdio(false);

     char c;

     while(scanf(" %c %s",&c,s)==)

     {

         init(c,s);

         int len=strlen(s);

         int ansl=,ansr=;

         manacher(s,len);

         if(mxx==)pf("No solution!\n");//回文长度是1

         else

         {

             int l=(id-mxx+)/-;

             int r=(id+mxx-)/-;

             pf("%d %d\n",l,r);

             f(i,l,r)pf("%c",s[i]);

             pf("\n");

 //            f(i,id-mxx+1,id+mxx-1)pf("%c",ma[i]);

 //            pf("\n");

         }

     }

  }