51nod 1089最长回文子串V2 (manacher)

经典题

manacher是一种很神奇的算法，

算是动态规划的一种，不过利用的信息非常有效

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 100;
char S2[maxn*2], str[maxn*2];
int R[maxn*2];
void Manacher(char* S){
    int L = strlen(S);
    for(int i = 0, j = 1; i < 2*L; i += 2, j += 2) S2[i] = '#', S2[j] = S[j/2];
    S2[2*L] = '#';
    int mx = -1, id = -1;
    for(int i = 0; i < 2*L; i++){
        R[i] = mx-i >= 0 ? min(R[2*id-i], mx-i+1) : 1;
        while(i+R[i] <= 2*L && S2[i+R[i]] == S2[i-R[i]]) R[i]++;
        if(i+R[i]-1 > mx) mx = i+R[i]-1, id = i;
    }
}

int main()
{
    cin>>str;
    Manacher(str);
    int L = strlen(str), ans = 0;
    //for(int i = 0; i < 2*L; i++) cout<<R[i]<<" "; cout<<endl;
    for(int i = 1; i < 2*L; i += 2) ans = max(ans, 2*(R[i]/2-1) + 1);
    for(int i = 0; i < 2*L; i += 2) ans = max(ans, R[i]-1);
    cout<<ans<<endl;
    return 0;
}