মানাচারের অ্যালগরিদম

একটি স্ট্রিং থেকে দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং খুঁজে পেতে, আমরা মানাচারের অ্যালগরিদম ব্যবহার করতে পারি। প্রতিটি অক্ষর নির্বাচন করে, আমরা বাম এবং ডান পয়েন্টার ব্যবহার করে কোন প্যালিনড্রোম আছে কিনা তা খুঁজে বের করার চেষ্টা করব। তথ্য সংরক্ষণ করার জন্য আরেকটি অ্যারে আছে, সেই তথ্য থেকে আমরা সহজেই জানতে পারি প্যালিনড্রোম কত লম্বা। প্রতিটি অক্ষরের জন্য, অ্যারে তথ্য সংরক্ষণ করবে। পুরো স্ট্রিংটি অতিক্রম করার পরে, আমরা তৈরি করা অ্যারে থেকে দীর্ঘতম প্যালিন্ড্রোমিক অনুক্রম খুঁজে পেতে পারি।

এই অ্যালগরিদমের সময় জটিলতা হল 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 << "Enter String:";
   cin >> mainString;
   palindrome = longestPalindrome(mainString);
   cout << "Longest palindrome is: " << palindrome << endl;
}

আউটপুট

Enter String: levelup
Longest palindrome is: level