hdoj-3068.最长回文

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input:输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output:每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input:
aaaa
abab

Sample Output:
4
3

注意到本题的数据范围是10^5级别的，用朴素的算法肯定是会超时的，那有没有高效地求解最长回文串的算法呢？下面介绍Manacher算法：

Manacher算法

注意到，对于一个回文串，可能有两种形式，第一种是aba，该回文串是以b这个字符为中心的，第二种是abba，它是以bb这两个字符为中心的，如此，为了统一处理这两种情况，我们需要对字符串进行一个预处理：

pic1

进行了这样的预处理之后，对于偶回文串，比如图中的aa，它在str中的形式是#a#a#，而对于奇回文串，比如图中的aba，它在str中的形式是#a#b#a#，那么在求最大回文串的过程中，我们将‘#'当作字符串的一部分就可以统一处理这两种形式的回文串。

引入几个核心变量

在马拉车算法中，我们引入这样几个变量：

1. rt: 表示当前的已经计算过的回文串a所触及到的最右边的位置的下一个位置
2.mid: 表示上面字符串a的回文中心
3.dp数组：表示每个字符的最大回文长度

我们根据一个例子来看这几个变量的作用：

pic2

根据定义我们得到上述字符串的dp数组：

pic3

同时根据上述的结果，我们很容易发现，原字符串中每个字符的最大回文长度就等于 $dp[i]-1$ 。

几个注意点

1.注意到#字符也是在我们处理中，所以我们需要在开头加上一个与#不同的字符。
2.为了避免边界问题，我们在字符末尾加上一个哨兵，也必须与#不同。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

const int N = 110100, M = N*2;

char s[N];   //原字符串
char str[M]; //预处理之后的字符串
int dp[M];
int m;

void Manacher(){
    int rt = 0, mid = 0;   //rt:当前的已经计算过的回文串a所触及到的最右边的位置的下一个位置，mid表示a的回文中心
    int res = 0;
    for(int i = 1; i<=m; i++){
        dp[i] = (i<rt? min(dp[mid*2-i],rt-i):1);
        while(str[i+dp[i]] == str[i-dp[i]]) dp[i]++;
        if(i+dp[i]> rt){
            rt = i+dp[i];
            mid = i;
        }
        res = max(res,dp[i]-1);
    }
    cout<<res<<endl;
}

int main()
{
    str[0] = '!';
    str[1] = '#';
    while(scanf("%s",s)!=EOF){
        
        int n = strlen(s);
        for(int i = 0; i<n; i++){
            str[i*2+2] = s[i];
            str[i*2+3] = '#';
        }

        m = n*2+1;
        str[m+1] = '@';
        Manacher();
    }    
    return 0;
}


// 原字符串s:    a  b  a  a
// 预处理串str:  #  a  #  b  #  a  #  a  #
// dp数组：      1  2  1  4  1  2  3  2  1