Manacher算法（O(n)求得最長回文）

Manacher算法：

  非常快的求回文字元串的算法，它和普通回文字元串檢索的差別就是，後者每個字元串的回文值（自定義為最長回文向左/右擴張長度）初始都是為1，而Manacher算法則可以利用前面已知的回文值，初始值不再僅僅是1，這就是其優化的地方。

  那麼怎麼利用前面已知的回文值得出有效資訊呢？看這篇文章吧 資料結構與算法系列----Manacher算法【O(n)求得最長回文】，感覺講的不錯，看的其他文章都太複雜了，這個簡潔明了，看了這個才懂了。

  在這注意到了自己一個不好的習慣，将strlen(str)放入for循環，會導緻逾時。

HDU-3068  最長回文

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

const int N = 110005;
char str[N],new_str[N*2];
int p[N*2];


int Manacher()
{
    int len = strlen(str);
    new_str[0] = '$';
    new_str[1] = '#';
    int num = 2;

    for (int i = 0; i < len; i++)
    {
        new_str[num++] = str[i];
        new_str[num++] = '#';
    }
    new_str[num] = '\0';


    int maxlen = 0;//最長回文長度
    int id,mx = 0;
    for (int i = 1; i < num; i++)
    {
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);
        else
            p[i] = 1;

        while (new_str[i - p[i]] == new_str[i + p[i]])//不需邊界判斷，因為左有'$',右有'\0'
            p[i]++;

        if (mx < i + p[i])//更新
        {
            id = i;
            mx = i + p[i];
        }

        maxlen = max(maxlen, p[i] - 1);
    }
    return maxlen;
}

int main()
{
    while (~scanf("%s", str))
    {
        printf("%d\n", Manacher());
    }
    return 0;
}
           

POJ-3974

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

const int N = 1000005;
char str[N],new_str[N*2];
int p[N*2];

int Manacher()
{
    int len = strlen(str);
    new_str[0] = '$';
    new_str[1] = '#';
    int num = 2;
    for(int i = 0;i < len;i++)
    {
        new_str[num++] = str[i];
        new_str[num++] = '#';
    }
    new_str[num] = '\0';

    int maxlen = 0;
    int id,mx = 0;
    for(int i = 1;i < num;i++)
    {
        if(mx > i)
            p[i] = min(p[id*2-i],mx - i);
        else
            p[i] = 1;

        while(new_str[i + p[i]] == new_str[i - p[i]])
            p[i]++;
        if(mx < i + p[i])
        {
            id = i;
            mx = i + p[i];
        }

        maxlen = max(maxlen,p[i]-1);
    }
    return maxlen;
}
int main()
{
    int ca = 1;
    while(~scanf("%s",str))
    {
        if(strcmp(str,"END") == 0)
            break;
        printf("Case %d: %d\n",ca++,Manacher());
    }
    return 0;
}