hdu 3068 最长回文

最长回文
题意:给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.字符串长度len <= 110000

最长回文串Manacher的裸题；

使用dp的思想对Manacher的理解:Manacher算法就是处理出前面以id为中点，半径为Mp[id]的回文串的右边界mx;之后每次处理i时，就可以看i是否在mx内，若是在mx里面，就可以将Mp[i]的初始值设置为i关于id对称的2*id-i处的点j，(之所以可以设置为对称的点j，是因为这两个点都在之前探索过的最长回文串之内，可以知道这两点在最长回文串内的左右字符是相同的)这时就可以从这个基础上向左右延伸了，否则朴素的算法就是每次Mp[i]都从0开始；很容易知道当i不在前面的回文串中，就不能利用前面得到的结果，只能从1开始；还有就是注下Ma[]的处理就行；

// 374MS   2652K   1041 B
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 1;i <= n;i++)
const int MAXN = 110011;
char Ma[MAXN<<1];
int Mp[MAXN<<1];
char ret[MAXN],s[MAXN];
void Manacher(const char s[],int len)
{
    int l = 0;
    Ma[l++] = '$';Ma[l++] = '#';//预处理不仅是为了不超出边界，并且还通过处理一边得到了整个回文串的长度~~
    rep(i,len){
        Ma[l++] = s[i];
        Ma[l++] = '#';
    }
    Ma[l] = '';
    int mx = 0,id;
    rep(i,l-1){
        Mp[i] = mx > i?min(mx-i,Mp[2*id-i]):1; // *** 设置位置i初始的对称长度；建立在相同'周边环境'的对称点j的基础之上
        while(Ma[i+Mp[i]] == Ma[i-Mp[i]]) Mp[i]++;//这就需要初始时[0] = '$'&[l] = ';
        if(i + Mp[i] > mx){
            mx = i + Mp[i];
            id = i;
        }
    }
}
int main()
{
    int len,i,j;
    while(scanf("%s",s+1) != EOF){
        len = strlen(s+1);
        Manacher(s,len);
        int ans = 0,id;
        for(i = 1;i < len*2;i++){
            if(ans < Mp[i])
                ans = Mp[i],id = i; //这里没有将 ans = Mp[i] - 1;而是在输出的时候，多一个'#'若为奇数，则多最终的'#';为偶数则多了中间的'#'
        }
        printf("%d
",--ans);
        /*id = id/2 - ans/2;  // 处理输出最长回文字符串；
        if(ans%2 == 0) id++;
        for(i = 0;i < ans;i++)
            putchar(s[id++]);*/
    }
    return 0;
}