经理的算法
要从字符串中找到最长的回文子字符串，我们可以使用Manacher算法。通过选择每个字符，我们将尝试使用左右指针查找是否有回文。还有另一种存储信息的数组，从这些信息中，我们可以轻松地找到回文的长度。对于每个字符，数组将存储信息。遍历整个字符串后，我们可以从创建的数组中找到最长的回文子序列。
该算法的时间复杂度为O(n)。
输入输出
Input: String: “levelup” Output: Longest palindrome is: level
算法
longestPalindrome(text)
输入-查找最长回文的文本
输出-文本中最长的常见回文
Begin
n := text size
if n = 0, then
return null string
n := 2n+1
define array longPal of size n
longPal[0] := 0 and longPal[1] := 1
centerIndex := 1
rightIndex := 2
right := 0
maxPalLength := 0
maxCenterIndex := 0
start := -1 and end := -1, diff := -1
for right := 2 to n-1, do
left := 2*centerIndex – right
longPal[right] := 0
diff := rightIndex – right
if diff > 0, then
longPal[right] := minimum(longPal[left], diff)
while (right + longPal[right]) < n AND (right - longPal[right]) > 0 AND
(right + longPal[right]+1)mod 2 = 0 OR
text[(right + longPal[right] + 1)/2] = text[(right - longPal[right]-1)/2], do
increase longPal[right] by 1
done
if longPal[right] > maxPalLength, then
maxPalLength := longPal[right]
maxCenterIndex := right
if (right + longPal[right]) > rightIndex, then
centerIndex := right
rightIndex := right + longPal[right]
done
start := (maxCenterIndex – maxPalLength)/2
end := start + maxPalLength – 1
palindrome = substring of text[start..end]
return palindrome
End示例
#include<iostream>
using namespace std;
int min(int a, int b) {
return (a<b)?a:b;
}
string longestPalindrome(string mainString) {
int n = mainString.size();
if(n == 0)
return "";
n = 2*n + 1; //count the next position
int longPal[n]; //array to store longest palindrome length
longPal[0] = 0; longPal[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; //calculate left position using center and right
longPal[right] = 0;
diff = rightIndex - right;
if(diff > 0)
longPal[right] = min(longPal[left], diff);
while ( ((right + longPal[right]) < n && (right - longPal[right]) > 0) &&
( ((right + longPal[right] + 1) % 2 == 0) ||
(mainString[(right + longPal[right] + 1)/2] == mainString[(right - longPal[right] - 1)/2] ))) {
longPal[right]++;
}
if(longPal[right] > maxPalLength) { //max palindrome length
maxPalLength = longPal[right];
axCenterIndex = right;
}
if (right + longPal[right] > rightIndex) {
centerIndex = right;
rightIndex = right + longPal[right];
}
}
start = (maxCenterIndex - maxPalLength)/2;
end = start + maxPalLength - 1;
string palindrome;
for(int i=start; i<=end; i++)
palindrome += mainString[i];
return palindrome;
}
int main(int argc, char *argv[]) {
string mainString, palindrome;
cout << "输入字符串：";
cin >> mainString;
palindrome = longestPalindrome(mainString);
cout << "Longest palindrome is: " << palindrome << endl;
}输出结果
输入字符串： levelup Longest palindrome is: level