hdu 3068 Manacher算法 O（n）回文子串算法

題目：http://acm.hdu.edu.cn/showproblem.php?pid=3068

關於算法的教程 推薦這個：http://blog.csdn.net/ggggiqnypgjg/article/details/6645824 注意：我推薦的這篇博客裡說的那個代碼有bug，我覺得沒問題，而是博主在用的時候寫錯了，博主舉得反例我都過了 而且hdu 3068也過了

最開始是用的後綴數組，2000ms+ 果斷超時...............

看過一遍很快就學會這個算法了：然後A掉

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

#define MAXN 200010

using namespace std;

int p[MAXN],n;
char str[MAXN],s[MAXN];

void pk()
{
    int mx=0,id;
    for(int i=n; str[i]!=0; i++)
        str[i] = 0;
    for(int i=1;ii)
            p[i]=min(p[id*2-i],mx-i);//這裡寫成min(id*2-i,mx-i)，WA得我快吐了 但是奇怪的是，還能跑328ms
        else
            p[i]=1;
        while(str[i-p[i]] == str[i+p[i]])p[i]++;
        if(i+p[i]>mx)
        {
            mx=p[i]+i;
            id=i;
        }
    }
}

void init()
{
    int i,j;
    n=strlen(s);
    str[0]='$';//標記開頭，可以用其他不會在測試樣例中出現的字符，同樣保證了在算p[i]的時候肯定不會越界，空字符肯定不等於$
    str[1]='#';//間隔,可以用其他不會在測試樣例中出現的字符
    for(i=0,j=2;i