九度OJ 1528 最长回文子串 -- Manacher算法

题目地址：http://ac.jobdu.com/problem.php?pid=1528

题目描述：: 回文串就是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

回文子串，顾名思义，即字符串中满足回文性质的子串。

给出一个只由小写英文字符a,b,c...x,y,z组成的字符串，请输出其中最长的回文子串的长度。

输入：: 输入包含多个测试用例，每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串，字符串的长度不大于200000。

输出：: 对于每组测试用例，输出一个整数，表示该组测试用例的字符串中所包含的的最长回文子串的长度。

样例输入：

abab

bbbb

abba

样例输出：

来源：: 腾讯2013年实习生招聘二面面试题

自己比较野蛮的方法

#include <stdio.h>

#include <string.h>

int LenOfMaxPalindrome(char str[], int len, int low, int high){

    int sum = 0;

    while (low >= 0 && high < len){

        if (str[low] == str[high]){

            sum += 2;

            --low;

            ++high;

        }

        else

            break;

    }

    return sum;

}

int MaxPalindrome (char str[]){

    int len = strlen (str);

    int mid;

    int len1;

    int len2;

    int max;

    if ((len >= 2) && (str[0] == str[1]))

        max = 2;

    else

        max = 1;

    for (mid=1; mid<len-1; ++mid){

        len1 = len2 = 0;

        len1 = LenOfMaxPalindrome(str, len, mid - 1, mid + 1) + 1;

        if (str[mid] == str[mid + 1]){

            len2 = LenOfMaxPalindrome(str, len, mid - 1, mid + 2) + 2;

        }

        if (len1 < len2)

            len1 = len2;

        if (max < len1)

            max = len1;

    }

    return max;

}

int main(void){

    char str[200001];

    while (scanf ("%s", str) != EOF){

        printf ("%d\n", MaxPalindrome (str));

    }

    return 0;

}

O(n)的回文子串Manacher算法（详细算法讲解见参考资料）

算法代码实现如下：

#include <stdio.h>

void Manacher (char str[], int len, int Radix[]){

    int mx = 0;    //记录被影响到的最远的位置

    int id = 0;    //最长影响串的位置

    Radix[0] = 0;

    int i;

    for (i=1; i<len; ++i){

        Radix[i] = 1;

        if (mx > i){

            Radix[i] = Radix[2 * id - i];

            if (mx - i < Radix[i])

                Radix[i] = mx - i;

        }

        while (str[i - Radix[i]] == str[i + Radix[i]])

            ++Radix[i];

        if (i + Radix[i] > mx){

            mx = i + Radix[i];

            id = i;

        }

    }

}

int Preproccess (char str[], char old_str[]){

    int index;

    int len;

    char middle = '#';

    str[0] = '$';

    str[1] = middle;

    index = 0;

    len = 2;

    while (old_str[index]){

        str[len++] = old_str[index++];

        str[len++] = middle;

    }

    str[len] = '?';

    return len;

}

int main(void){

    char old_str[200001];

    char str[400004];

    int Radix[400004];

    int len;

    int i;

    int ans;

    while (scanf ("%s", old_str) != EOF){

         len = Preproccess (str, old_str);

         Manacher (str, len, Radix);

         ans = 0;

         for (i=1; i<len; ++i){

            if (ans < Radix[i])

                ans = Radix[i];

         }

         printf ("%d\n", ans - 1);

    }

    return 0;

}