Thuật toán của Manacher

Để tìm chuỗi con palindromic dài nhất từ ​​một chuỗi, chúng ta có thể sử dụng Thuật toán Manacher. Bằng cách chọn từng ký tự, chúng tôi sẽ cố gắng tìm xem có palindrome nào không bằng cách sử dụng con trỏ trái và phải. Có một mảng khác để lưu trữ thông tin, từ thông tin đó chúng ta có thể dễ dàng tìm ra palindrome dài bao nhiêu. Với mỗi ký tự, mảng sẽ lưu trữ thông tin. Sau khi duyệt qua toàn bộ chuỗi, chúng ta có thể tìm thấy dãy con palindromic dài nhất từ ​​mảng đã tạo.

Độ phức tạp về thời gian của thuật toán này là O (n).

Đầu vào và Đầu ra

Input:
String: “levelup”
Output:
Longest palindrome is: level

Thuật toán

longestPalindrome(text)

Đầu vào - Văn bản để tìm palindrome dài nhất

Đầu ra - Palindrome dài nhất trong văn bản

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

Ví dụ

#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 << "Enter String:";
   cin >> mainString;
   palindrome = longestPalindrome(mainString);
   cout << "Longest palindrome is: " << palindrome << endl;
}

Đầu ra

Enter String: levelup
Longest palindrome is: level