马拉车算法（C/C++）

#1024程序员节 | 征文#

马拉车算法（Manacher's Algorithm）是一种用于在字符串中查找最长回文子串的线性时间复杂度算法。该算法由Udi Manacher在1980年代提出，因此得名。它的核心思想是利用已知的回文信息来减少不必要的比较，从而提高效率。

算法步骤

1. 预处理字符串： 为了处理奇数长度和偶数长度的回文串，算法首先对输入字符串进行预处理。在每个字符之间插入一个特殊字符（通常是#），并在字符串的开头和结尾也各插入一个。这样做的目的是为了让每个字符都有一个唯一的中心位置。

2. 初始化变量：

   • p[]：一个数组，用于存储每个位置的回文半径。
   • C：当前考虑的中心位置。
   • R：当前考虑的右端点，即以C为中心的回文串的最右端。

3. 遍历字符串： 对于预处理后的字符串中的每个位置i，算法尝试找到以i为中心的回文串的半径。这个过程分为两步：

   • 利用已知的回文信息：如果i在当前考虑的回文串内（即i < R），则可以利用对称位置的回文半径来减少比较次数。
   • 扩展回文串：如果i不在当前考虑的回文串内，或者需要进一步扩展回文串，算法会尝试扩展以i为中心的回文串，直到无法进一步扩展。

4. 更新最大回文串： 在遍历过程中，如果找到的回文串半径大于之前记录的最大半径，则更新最大回文串的起始位置和半径。

5. 提取最长回文子串： 遍历完成后，根据记录的最大半径和起始位置，从原始字符串中提取最长的回文子串。

算法详解

• 中心扩展思想：马拉车算法利用了中心扩展的思想，即以每个字符为中心，向两边扩展，直到无法形成回文串为止。这种方法可以避免重复比较相同的字符对。

• 利用对称性：算法利用了回文串的对称性，即如果以i为中心的回文串已知，那么以2*C - i为中心的回文串的半径至少与以C为中心的回文串的半径相同。这里C是当前考虑的中心位置。

• 动态规划：虽然马拉车算法不是传统意义上的动态规划算法，但它的思想与动态规划类似，即利用之前计算的结果来简化当前的计算。

复杂度分析

• 时间复杂度：O(n)，其中n是输入字符串的长度。这是因为每个位置的回文半径只计算一次。
• 空间复杂度：O(n)，用于存储回文半径的数组。

代码实现：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string manacher(const string& s) {
    if (s.empty()) return s;
    
    // 预处理字符串，插入特殊字符
    string t = "#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    int n = t.length();
    vector<int> p(n, 0);
    int C = 0, R = 0; // C为当前回文的中心，R为当前回文的右边界
    int maxLen = 0, centerIndex = 0;
    
    for (int i = 1; i < n; i++) {
        if (i < R) {
            int mirror = 2 * C - i;
            p[i] = min(R - i, p[mirror]);
        }
        int left = i - p[i], right = i + p[i];
        while (left >= 1 && right < n - 1 && t[left - 1] == t[right + 1]) {
            p[i]++;
            left--;
            right++;
        }
        if (i + p[i] > R) {
            C = i;
            R = i + p[i];
        }
        if (p[i] > maxLen) {
            maxLen = p[i];
            centerIndex = i;
        }
    }
    
    // 从预处理的字符串中提取最长回文子串
    int start = (centerIndex - maxLen) / 2;
    return s.substr(start, maxLen - 1); // 减1是因为预处理字符串中插入了特殊字符
}

int main() {
    string s;
    cin >> s;
    cout << manacher(s) << endl;
    return 0;
}

应用实例：

在LeetCode上的题目“5. Longest Palindromic Substring”就是一个典型的应用实例，要求找出给定字符串中的最长回文子串。马拉车算法可以应用于生物信息学中DNA序列的回文结构分析，以及文本处理中的回文检测等场景。该算法也可以用于解决其他与回文相关的问题，如找出所有回文子串、判断回文对等。

算法实现部分：

string manacher(string s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    vector<int> p(t.size(), 0);
    int C = 0, R = 0;
    int maxLen = 0, centerIndex = 0;
    for (int i = 1; i < t.size(); i++) {
        if (i < R) p[i] = min(p[2 * C - i], R - i);
        else p[i] = 1;
        while (t[i + p[i]] == t[i - p[i]]) p[i]++;
        if (i + p[i] > R) {
            C = i;
            R = i + p[i];
        }
        if (p[i] > maxLen) {
            maxLen = p[i];
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2;
    return s.substr(start, maxLen - 1);
}

马拉车算法是解决最长回文子串问题的有效方法，其线性时间复杂度使其在处理大规模数据时具有明显优势。文章到此为止感谢大家的支持。