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數組的內容。這個數組表示了以每個字符為中心的最長回文子串的半徑。