输出字符串中最长回文串的长度。Manacher 算法 用c编写

Manacher 算法是一种用于求解字符串中最长回文子串长度的算法。它的时间复杂度为 O(n)，其中 n 为字符串的长度。

下面是用 C 语言实现 Manacher 算法的代码：

#include <stdio.h>
#include <string.h>

#define MAX_N 1000000

char str[MAX_N+5];
int p[MAX_N+5];

int manacher(char *s)
{
    int mx = 0, id = 0, res = 0;
    for (int i = 1; s[i]; i++)
    {
        if (mx > i) p[i] = p[2*id-i] < mx-i ? p[2*id-i] : mx-i;
        else p[i] = 1;
        while (s[i-p[i]] == s[i+p[i]]) p[i]++;
        if (i+p[i] > mx)
        {
            mx = i+p[i];
            id = i;
        }
        res = res > p[i] ? res : p[i];
    }
    return res-1;
}

int main()
{
    scanf("%s", str+1);
    printf("%d\n", manacher(str));
    return 0;
}

在这段代码中，我们将原字符串复制一遍，并在两边添加不同的字符（如 #），这样就可以将所有的回文子串看作是奇数长度的回文子串。接下来，我们使用一个数组 p 来记录以每个字符为中心的回文子串的最大长度，最后扫描一遍 p 数组，取出最大值就是我们要求的答案。

希望这段代码对你有帮助。