C语言实现Manacher最长回文子串算法

在字符串处理中，寻找最长回文子串是一个经典的问题。Manacher算法是一种高效的算法，用于在给定字符串中找到最长的回文子串。相较于暴力解法，Manacher算法将时间复杂度从O(n^2)降低到了O(n)，大大提高了计算效率。本文将详细介绍如何使用C语言实现Manacher最长回文子串算法，包括基础概念、使用方法、常见实践以及最佳实践。

简介

在字符串处理中，寻找最长回文子串是一个经典的问题。Manacher算法是一种高效的算法，用于在给定字符串中找到最长的回文子串。相较于暴力解法，Manacher算法将时间复杂度从$O(n^2)$降低到了$O(n)$，大大提高了计算效率。本文将详细介绍如何使用C语言实现Manacher最长回文子串算法，包括基础概念、使用方法、常见实践以及最佳实践。

基础概念
- 回文子串
- Manacher算法核心思想
使用方法
- 预处理字符串
- 计算回文半径数组
- 找到最长回文子串
常见实践
- 处理不同类型的输入字符串
- 优化空间复杂度
最佳实践
- 代码优化技巧
- 边界条件处理
代码示例
小结
参考资料

基础概念

回文子串

回文子串是字符串中从左到右和从右到左读起来都一样的子串。例如，在字符串 “abba” 中，“abba”、“bb” 都是回文子串；在字符串 “abcba” 中，“abcba”、“bcb”、“c” 都是回文子串。

Manacher算法核心思想

Manacher算法的核心思想是通过利用已经计算出的回文子串信息，避免重复计算，从而达到线性时间复杂度。算法首先对原始字符串进行预处理，在每个字符之间插入一个特殊字符（如 ’#’），这样可以将奇数长度和偶数长度的回文子串统一处理。然后通过维护一个回文半径数组 p[]，p[i] 表示以第 i 个字符为中心的最长回文子串的半径（包含自身）。

使用方法

预处理字符串

为了统一处理奇数长度和偶数长度的回文子串，我们需要对原始字符串进行预处理。在每个字符之间插入一个特殊字符（如 ’#’），并在字符串的开头和结尾也插入特殊字符。例如，对于字符串 “abba”，预处理后的字符串为 “#a#b#b#a#“。

// 预处理字符串
char* preProcess(char* s) {
    int len = strlen(s);
    char* newS = (char*)malloc((2 * len + 3) * sizeof(char));
    newS[0] = '@';
    newS[1] = '#';
    int j = 2;
    for (int i = 0; i < len; i++) {
        newS[j++] = s[i];
        newS[j++] = '#';
    }
    newS[j] = '$';
    newS[j + 1] = '\0';
    return newS;
}

计算回文半径数组

计算回文半径数组 p[]，p[i] 表示以第 i 个字符为中心的最长回文子串的半径（包含自身）。通过维护一个当前最右边界 right 和其对应的中心 center，利用回文的对称性来快速计算 p[i]。

// 计算回文半径数组
void manacher(char* s, int* p) {
    int len = strlen(s);
    int center = 0, right = 0;
    for (int i = 1; i < len - 1; i++) {
        int iMirror = 2 * center - i;
        if (right > i) {
            p[i] = min(right - i, p[iMirror]);
        } else {
            p[i] = 1;
        }
        while (s[i + p[i]] == s[i - p[i]]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
}

找到最长回文子串

遍历回文半径数组 p[]，找到最大的半径值，从而确定最长回文子串的长度和位置。然后从预处理后的字符串中提取出最长回文子串，并将其还原为原始字符串中的形式。

// 找到最长回文子串
char* findLongestPalindrome(char* s) {
    char* newS = preProcess(s);
    int len = strlen(newS);
    int* p = (int*)malloc(len * sizeof(int));
    manacher(newS, p);
    int maxLen = 0, centerIndex = 0;
    for (int i = 1; i < len - 1; i++) {
        if (p[i] - 1 > maxLen) {
            maxLen = p[i] - 1;
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2;
    char* result = (char*)malloc((maxLen + 1) * sizeof(char));
    strncpy(result, s + start, maxLen);
    result[maxLen] = '\0';
    free(newS);
    free(p);
    return result;
}

常见实践

处理不同类型的输入字符串

Manacher算法可以处理包含各种字符的字符串，包括字母、数字、标点符号等。只需确保预处理和处理过程中对所有字符都进行一致的操作。

优化空间复杂度

在实现过程中，我们可以通过复用数组来优化空间复杂度。例如，在计算回文半径数组时，可以直接在预处理后的字符串数组上进行操作，而不需要额外开辟一个数组来存储回文半径。

最佳实践

代码优化技巧

减少不必要的计算：在计算回文半径时，利用回文的对称性尽量减少重复计算。
边界条件处理：在预处理和计算过程中，要注意处理字符串的开头和结尾，避免越界访问。

边界条件处理

空字符串处理：当输入为空字符串时，直接返回空字符串。
单个字符字符串处理：当输入为单个字符字符串时，直接返回该字符。

代码示例

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

// 辅助函数：返回两个数中的较小值
int min(int a, int b) {
    return a < b? a : b;
}

// 预处理字符串
char* preProcess(char* s) {
    int len = strlen(s);
    char* newS = (char*)malloc((2 * len + 3) * sizeof(char));
    newS[0] = '@';
    newS[1] = '#';
    int j = 2;
    for (int i = 0; i < len; i++) {
        newS[j++] = s[i];
        newS[j++] = '#';
    }
    newS[j] = '$';
    newS[j + 1] = '\0';
    return newS;
}

// 计算回文半径数组
void manacher(char* s, int* p) {
    int len = strlen(s);
    int center = 0, right = 0;
    for (int i = 1; i < len - 1; i++) {
        int iMirror = 2 * center - i;
        if (right > i) {
            p[i] = min(right - i, p[iMirror]);
        } else {
            p[i] = 1;
        }
        while (s[i + p[i]] == s[i - p[i]]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
}

// 找到最长回文子串
char* findLongestPalindrome(char* s) {
    if (s == NULL || strlen(s) == 0) {
        return "";
    }
    if (strlen(s) == 1) {
        return s;
    }
    char* newS = preProcess(s);
    int len = strlen(newS);
    int* p = (int*)malloc(len * sizeof(int));
    manacher(newS, p);
    int maxLen = 0, centerIndex = 0;
    for (int i = 1; i < len - 1; i++) {
        if (p[i] - 1 > maxLen) {
            maxLen = p[i] - 1;
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2;
    char* result = (char*)malloc((maxLen + 1) * sizeof(char));
    strncpy(result, s + start, maxLen);
    result[maxLen] = '\0';
    free(newS);
    free(p);
    return result;
}

int main() {
    char s[] = "babad";
    char* result = findLongestPalindrome(s);
    printf("最长回文子串: %s\n", result);
    free(result);
    return 0;
}

小结

本文详细介绍了C语言实现Manacher最长回文子串算法，包括基础概念、使用方法、常见实践以及最佳实践。通过预处理字符串、计算回文半径数组和找到最长回文子串等步骤，我们可以高效地解决最长回文子串问题。在实际应用中，要注意处理不同类型的输入字符串和优化代码的空间复杂度和时间复杂度。