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

#1024程序员节 | 征文#

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

算法步骤

预处理字符串：为了处理奇数长度和偶数长度的回文串，算法首先对输入字符串进行预处理。在每个字符之间插入一个特殊字符（通常是#），并在字符串的开头和结尾也各插入一个。这样做的目的是为了让每个字符都有一个唯一的中心位置。
初始化变量：
- p[]：一个数组，用于存储每个位置的回文半径。
- C：当前考虑的中心位置。
- R：当前考虑的右端点，即以C为中心的回文串的最右端。
遍历字符串：对于预处理后的字符串中的每个位置i，算法尝试找到以i为中心的回文串的半径。这个过程分为两步：
- 利用已知的回文信息：如果i在当前考虑的回文串内（即i < R），则可以利用对称位置的回文半径来减少比较次数。
- 扩展回文串：如果i不在当前考虑的回文串内，或者需要进一步扩展回文串，算法会尝试扩展以i为中心的回文串，直到无法进一步扩展。
更新最大回文串：在遍历过程中，如果找到的回文串半径大于之前记录的最大半径，则更新最大回文串的起始位置和半径。
提取最长回文子串：遍历完成后，根据记录的最大半径和起始位置，从原始字符串中提取最长的回文子串。

算法详解

中心扩展思想：马拉车算法利用了中心扩展的思想，即以每个字符为中心，向两边扩展，直到无法形成回文串为止。这种方法可以避免重复比较相同的字符对。
利用对称性：算法利用了回文串的对称性，即如果以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);
}

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