经理的算法

要从字符串中找到最长的回文子字符串，我们可以使用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