C语言字符串中的Manacher算法

Manacher算法是一种用于查找字符串中最长回文子串的线性时间复杂度算法。它的基本思想是利用已经计算出的回文子串的信息，避免重复计算。Manacher算法的时间复杂度为O(n)，其中n为字符串的长度。

以下是Manacher算法的实现：

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

void Manacher(char *str, int *P) {
    int n = strlen(str);
    int center = 0; // 回文中心
    int maxRight = 0; // 回文右边界
    int maxLen = 0; // 最长回文子串长度
    int maxCenter = 0; // 最长回文子串中心

    for (int i = 0; i < n; ++i) {
        if (i < maxRight) {
            int mirror = 2 * center - i; // 镜像位置
            P[i] = min(maxRight - i, P[mirror]);
        } else {
            P[i] = 1;
        }

        while (i - P[i] >= 0 && i + P[i] < n && str[i - P[i]] == str[i + P[i]]) {
            ++P[i];
        }

        if (i + P[i] > maxRight) {
            center = i;
            maxRight = i + P[i];
        }

        if (P[i] > maxLen) {
            maxLen = P[i];
            maxCenter = i;
        }
    }
}

int main() {
    char str[] = "babad";
    int n = strlen(str);
    int P[n];

    Manacher(str, P);

    for (int i = 0; i < n; ++i) {
        printf("%d ", P[i]);
    }
    printf("\n");

    return 0;
}

在这个例子中，我们首先定义了一个名为Manacher的函数，它接受一个字符串指针str和一个整数数组指针P作为参数。P数组用于存储以每个字符为中心的最长回文子串的半径（包括中心字符）。

在Manacher函数中，我们首先初始化了一些变量，如回文中心、回文右边界、最长回文子串长度和最长回文子串中心。然后，我们遍历字符串中的每个字符，根据已知的回文子串信息计算以当前字符为中心的最长回文子串的半径，并更新相关变量。

在main函数中，我们调用Manacher函数，并打印出P数组的内容。这个数组表示了以每个字符为中心的最长回文子串的半径。