一、基本介绍
Manacher算法，又称为马拉车算法（Manacher’s Algorithm），是一种用于在字符串中查找最长回文子串的算法，时间复杂度为O(n)。该算法的核心思想是基于已知的回文子串来扩展新的回文子串。
二、算法思想
Manacher算法的核心思想是基于已知的对称中心扩展回文子串。我们会对每个字符进行处理，以该字符为中心，分为两种情况：
1、如果这个字符在之前的某一个回文子串中（不一定是最长的），则我们可以利用这个已知信息，将这个字符作为以当前字符为中心的回文子串的起点。
2、如果这个字符没有出现在之前的任何回文子串中，那么我们需要拓展以这个字符为中心的回文子串的长度。在这个过程中，我们需要判断以当前字符为中心的回文子串的长度，并记录下来以备后用。
三、核心代码
以下是Manacher算法的核心代码，代码中使用两个数组记录当前已知的最长回文半径和对应的回文串。
string manacher(string& s) {
string t = "$#";
for (auto& c : s) {
t += c;
t += '#';
}
int n = t.size();
vector p(n);
int mx = 0, id = 0, resLen = 0, resCenter = 0;
for (int i = 1; i i ? min(p[2 * id - i], mx - i) : 1;
while (t[i + p[i]] == t[i - p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (resLen < p[i]) {
resLen = p[i];
resCenter = i;
}
}
return s.substr((resCenter - resLen) / 2, resLen - 1);
}
四、优化 – Manacher算法优化
在实际应用中，可以通过预处理的方式，优化Manacher算法，可以大大降低计算量，加快计算速度。
具体优化方法是先将字符串预处理，将相邻的相同字符进行压缩，避免重复计算。此外，通过添加虚拟字符，避免中心是一个字符时需要特殊处理的情况。
string manacher(string& s) {
int n = s.size();
string t;
t += '#';
for (int i = 0; i < n; i++) {
t += s[i];
t += '#';
}
n = t.size();
vector p(n);
int mx = 0, id = 0, resLen = 0, resCenter = 0;
for (int i = 1; i i)
p[i] = min(mx - i, p[2 * id - i]);
else
p[i] = 1;
while (t[i + p[i]] == t[i - p[i]])
p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
if (p[i] > resLen) {
resLen = p[i];
resCenter = i;
}
}
return s.substr((resCenter - resLen) / 2, resLen - 1);
}
五、实际应用
Manacher算法可以解决多种应用问题，例如回文字符串匹配、最长回文子序列、最长回文子串等等。此外，Manacher算法还可以用于字符串压缩，比如将重复的段落（如HTML中的）进行压缩，缩短文本长度。
六、总结
Manacher算法是一种高效的查找最长回文子串的算法，时间复杂度为O(n)。通过预处理和优化，可以进一步提高计算效率。Manacher算法在实际应用中非常广泛，可以解决回文字符串匹配、最长回文子序列、最长回文子串等问题。
原创文章，作者：FWDNB，如若转载，请注明出处：https://www.506064.com/n/331639.html
微信扫一扫 
支付宝扫一扫 