HDU 3068 最長回文(Manacher)

HDU 3068 最長回文(Manacher)

題意

給出一個只由小寫英文字符a,b,c…y,z組成的字符串S,求S中最長回文串的長度.
回文就是正反讀都是一樣的字符串,如aba, abba等

思路

用特殊字符插入到s串中每兩個字符中間，實現每個回文串都是奇數，再用manacher算法進行求解。

代碼

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 110009;
char s[N], t[N<<1];
int p[N<<1];

int manacher(int len)
{
    int id = 1, mx=0;
    p[0] = 1;
    for(int i=1; i i)
            p[i] = min(mx-i, p[2*id-i]);
        else
            p[i] = 1;
        while(t[i+p[i]] == t[i-p[i]])
            p[i]++;
        if(mx < p[i]+i)
        {
            mx = p[i]+i;
            id = i;
        }
    }
    int ans = p[1];
    for(int i=1; i