อัลกอริทึมของ Manacher

ในการค้นหาสตริงย่อยพาลินโดรมที่ยาวที่สุดจากสตริง เราสามารถใช้อัลกอริทึมของ Manacher โดยการเลือกอักขระแต่ละตัว เราจะพยายามค้นหาว่ามี palindrome ตัวใดที่ใช้ตัวชี้ซ้ายและขวา มีอาร์เรย์อื่นสำหรับเก็บข้อมูล จากข้อมูลนั้นเราสามารถค้นหา palindrome ได้อย่างง่ายดาย สำหรับอักขระแต่ละตัว อาร์เรย์จะเก็บข้อมูล หลังจากข้ามผ่านทั้งสตริง เราจะพบลำดับย่อยพาลินโดรมที่ยาวที่สุดจากอาร์เรย์ที่สร้างขึ้น

ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ O(n)

อินพุตและเอาต์พุต

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

อัลกอริทึม

longestPalindrome(text)

ป้อนข้อมูล - ข้อความค้นหาพาลินโดรมที่ยาวที่สุด

ผลลัพธ์ − palindrome ทั่วไปที่ยาวที่สุดในข้อความ

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

ผลลัพธ์

Enter String: levelup
Longest palindrome is: level