Manacher 算法
Manacher 算法用于查找给定字符串中的最长回文子串。回文是指与其逆序相等的字符串，而回文子串是指字符串中本身也是回文的子串，例如"aabaaccaabaa"中的"aabaa"。该算法由 Glenn K. Manacher 于 1975 年提出。
Manacher 算法的工作原理是什么？
查找最长回文子串的简单方法是检查给定字符串中所有可能的子串，然后验证它是否是回文。然而，这会消耗更多的时间和空间。
Manacher 算法通过一些观察和技巧，以线性时间（即 O(n)）解决了这个问题。其主要思想是利用回文的对称性来避免不必要的比较。
算法
Manacher 算法 − 包含以下步骤
首先，我们对给定的字符串进行预处理，在每对字符之间以及字符串的首尾插入一个特殊字符，例如"#"。这确保新字符串中的每个回文长度均为奇数，且中心点唯一。例如，字符串"abba"变为"#a#b#b#a#"。
接下来，我们创建一个名为 P[] 的数组，其长度与新字符串相同，其中 P[i] 存储新字符串中以位置 i 为中心的最长回文子字符串的长度。我们初始化 P[0] = 0 和 P[1] = 1，因为前两个字符始终是单字符回文串。
然后，我们从左到右迭代新字符串。
对于每个位置 i，找到 i 相对于当前最右边回文串中心的镜像位置 j。
接下来，将 P[j] 的值复制到 P[i]，除非它超出边界 R。
通过比较 i + P[i] 两侧的字符，扩展以 i 为中心的回文串。如果匹配，我们将 P[i] 加 1，并重复此步骤，直到它们不匹配或到达字符串末尾。
示例
在下面的示例中，我们将实际演示 Manacher 算法在各种编程语言中的工作原理。
#include<stdio.h>
#include<string.h>
// 返回两个整数中最小值的函数
int minm(int a, int b) {
return (a<b)?a:b;
}
// 查找最长回文子串的函数
void findLongPalindrome(char orgnlString[]) {
int n = strlen(orgnlString);
if(n == 0)
// 如果字符串为空，则返回空字符串
return;
n = 2*n + 1;
// 存储回文长度的数组
int lenPalndrm[n];
// 初始化前两个位置
lenPalndrm[0] = 0; lenPalndrm[1] = 1;
int centerIndex = 1;
int rightIndex = 2;
int right = 0, left;
int maxPalLength = 0, maxCenterIndex = 0;
int start = -1, end = -1, diff = -1;
// 循环遍历字符串
for (right = 2; right < n; right++) {
left = 2*centerIndex-right;
lenPalndrm[right] = 0;
diff = rightIndex - right;
// 如果差值大于 0，则更新当前位置的长度
if(diff > 0)
lenPalndrm[right] = minm(lenPalndrm[left], diff);
//虽然回文可以扩展，但可以扩展它
while ( ((right + lenPalndrm[right]) < n && (right - lenPalndrm[right]) > 0) &&
( ((right + lenPalndrm[right] + 1) % 2 == 0) ||
(orgnlString[(right + lenPalndrm[right] + 1)/2] == orgnlString[(right - lenPalndrm[right] - 1)/2] ))) {
lenPalndrm[right]++;
}
// 如果当前位置的回文长度大于最大回文长度，则更新最大回文长度及其中心索引
if(lenPalndrm[right] > maxPalLength) {
maxPalLength = lenPalndrm[right];
maxCenterIndex = right;
}
// 如果当前位置回文的右边界大于右索引，则更新中心索引和右索引
if (right + lenPalndrm[right] > rightIndex) {
centerIndex = right;
rightIndex = right + lenPalndrm[right];
}
}
start = (maxCenterIndex - maxPalLength)/2;
end = start + maxPalLength - 1;
// maximum palindrome
char maxPalindrm[end-start+2];
strncpy(maxPalindrm, &orgnlString[start], end-start+1);
maxPalindrm[end-start+1] = '\0';
printf("最长回文是： %s
", maxPalindrm);
}
int main() {
char orgnlString[] = "AAAABCAEAAABCBDDAAAAABC";
// method calling
findLongPalindrome(orgnlString);
return 0;
}
#include<iostream>
using namespace std;
// 返回两个整数中最小值的函数
int minm(int a, int b) {
return (a<b)?a:b;
}
// 查找最长回文子串的函数
string findLongPalindrome(string orgnlString) {
int n = orgnlString.size();
if(n == 0)
// 如果字符串为空，则返回空字符串
return "";
n = 2*n + 1;
// 存储回文长度的数组
int lenPalndrm[n];
// 初始化前两个位置
lenPalndrm[0] = 0; lenPalndrm[1] = 1;
int centerIndex = 1;
int rightIndex = 2;
// 用于存储当前左右位置的变量
int right = 0, left;
// 用于存储最大回文长度及其中心索引的变量
int maxPalLength = 0, maxCenterIndex = 0;
int start = -1, end = -1, diff = -1;
// 循环遍历字符串
for (right = 2; right < n; right++) {
// 计算相应的左侧位置
left = 2*centerIndex-right;
lenPalndrm[right] = 0;
diff = rightIndex - right;
// 如果差值大于 0，则更新当前位置的长度
if(diff > 0)
lenPalndrm[right] = min(lenPalndrm[left], diff);
//虽然回文可以扩展，但可以扩展它
while ( ((right + lenPalndrm[right]) < n && (right - lenPalndrm[right]) > 0) &&
( ((right + lenPalndrm[right] + 1) % 2 == 0) ||
(orgnlString[(right + lenPalndrm[right] + 1)/2] == orgnlString[(right - lenPalndrm[right] - 1)/2] ))) {
lenPalndrm[right]++;
}
// 如果当前位置的回文长度大于最大回文长度，则更新最大回文长度及其中心索引
if(lenPalndrm[right] > maxPalLength) {
maxPalLength = lenPalndrm[right];
maxCenterIndex = right;
}
// 如果当前位置回文的右边界大于右索引，则更新中心索引和右索引
if (right + lenPalndrm[right] > rightIndex) {
centerIndex = right;
rightIndex = right + lenPalndrm[right];
}
}
// 计算最大回文数的起始和结束索引
start = (maxCenterIndex - maxPalLength)/2;
end = start + maxPalLength - 1;
string maxPalindrm;
// 构造最大回文数
for(int i=start; i<=end; i++)
maxPalindrm += orgnlString[i];
// 返回最大回文数
return maxPalindrm;
}
int main(int argc, char *argv[]) {
string orgnlString, palindrome;
orgnlString = "AAAABCAEAAABCBDDAAAAABC";
// method calling
palindrome = findLongPalindrome(orgnlString);
cout << "最长回文是： " << palindrome << endl;
}
import java.util.Arrays;
public class Main {
// 查找最长回文子串的函数
public static String findLongestPalindrome(String orgnlString) {
// 如果字符串为空或为空，则返回空字符串
if (orgnlString == null || orgnlString.length() == 0)
return "";
char[] s2 = addBoundaries(orgnlString.toCharArray());
// 存储回文长度的数组
int[] lenPlandrm = new int[s2.length];
int centerIndex = 0, right = 0;
// 比较两个元素是否相同
int m = 0, n = 0;
// 循环遍历字符串
for (int i = 1; i<s2.length; i++) {
if (i > right) {
lenPlandrm[i] = 0; m = i - 1; n = i + 1;
} else {
int i2 = centerIndex * 2 - i;
if (lenPlandrm[i2] < (right - i - 1)) {
lenPlandrm[i] = lenPlandrm[i2];
m = -1;
} else {
lenPlandrm[i] = right - i;
n = right + 1; m = i * 2 - n;
}
}
//虽然回文可以扩展，但可以扩展它
while (m >= 0 && n < s2.length && s2[m] == s2[n]) {
lenPlandrm[i]++; m--; n++;
}
// 如果当前位置回文的右边界大于右索引，则更新中心索引和右索引
if ((i + lenPlandrm[i]) > right) {
centerIndex = i; right = i + lenPlandrm[i];
}
}
int len = 0; centerIndex = 0;
// 找到最大回文长度及其中心索引
for (int i = 1; i<s2.length; i++) {
if (len < lenPlandrm[i]) {
len = lenPlandrm[i]; centerIndex = i;
}
}
// 构造最大回文数
char[] maxPalindrm = Arrays.copyOfRange(s2, centerIndex - len, centerIndex + len + 1);
// 返回最大回文数
return String.valueOf(removeBoundaries(maxPalindrm));
}
// 添加边界以处理偶数长度回文的函数
private static char[] addBoundaries(char[] cs) {
if (cs == null || cs.length == 0)
return "||".toCharArray();
char[] cs2 = new char[cs.length * 2 + 1];
for (int i = 0; i < (cs2.length - 1); i = i + 2) {
cs2[i] = '|';
cs2[i + 1] = cs[i / 2];
}
cs2[cs2.length - 1] = '|';
return cs2;
}
// 从结果中删除添加的边界的函数
private static char[] removeBoundaries(char[] cs) {
if (cs == null || cs.length < 3)
return "".toCharArray();
char[] cs2 = new char[(cs.length - 1) / 2];
for (int i = 0; i < cs2.length; i++) {
cs2[i] = cs[i * 2 + 1];
}
return cs2;
}
public static void main(String[] args) {
String orgnlString = "AAAABCAEAAABCBDDAAAAABC";
System.out.println("最长回文是： " + findLongestPalindrome(orgnlString));
}
}
def add_boundaries(cs):
if cs is None or len(cs) == 0:
return ['|', '|']
cs2 = ['|'] * (len(cs) * 2 + 1)
for i in range(len(cs)):
cs2[i * 2 + 1] = cs[i]
return cs2
def remove_boundaries(cs):
if cs is None or len(cs) < 3:
return ""
cs2 = [''] * ((len(cs) - 1) // 2)
for i in range(len(cs2)):
cs2[i] = cs[i * 2 + 1]
return ''.join(cs2)
def find_longest_palindrome(orgnl_string):
if orgnl_string is None or len(orgnl_string) == 0:
return ""
s2 = add_boundaries(list(orgnl_string))
len_palandrm = [0] * len(s2)
center_index = 0
right = 0
m = 0
n = 0
for i in range(1, len(s2)):
if i > right:
len_palandrm[i] = 0
m = i - 1
n = i + 1
else:
i2 = center_index * 2 - i
if len_palandrm[i2] < (right - i - 1):
len_palandrm[i] = len_palandrm[i2]
m = -1
else:
len_palandrm[i] = right - i
n = right + 1
m = i * 2 - n
while m >= 0 and n < len(s2) and s2[m] == s2[n]:
len_palandrm[i] += 1
m -= 1
n += 1
if (i + len_palandrm[i]) > right:
center_index = i
right = i + len_palandrm[i]
length = 0
center_index = 0
for i in range(1, len(s2)):
if length < len_palandrm[i]:
length = len_palandrm[i]
center_index = i
max_palindrm = s2[center_index - length : center_index + length + 1]
return remove_boundaries(max_palindrm)
orgnl_string = "AAAABCAEAAABCBDDAAAAABC"
print("最长回文是：", find_longest_palindrome(orgnl_string))
Output
最长回文是： AAAAA
