मनचेर का एल्गोरिथम

एक स्ट्रिंग से सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग को खोजने के लिए, हम Manacher's Algorithm का उपयोग कर सकते हैं। प्रत्येक वर्ण का चयन करके, हम यह पता लगाने की कोशिश करेंगे कि क्या बाएँ और दाएँ सूचक का उपयोग करते हुए कोई पैलिंड्रोम है। जानकारी संग्रहीत करने के लिए एक और सरणी है, उस जानकारी से हम आसानी से पता लगा सकते हैं कि पैलिंड्रोम कितना लंबा है। प्रत्येक वर्ण के लिए, सरणी जानकारी संग्रहीत करेगी। पूरे स्ट्रिंग को पार करने के बाद, हम बनाए गए सरणी से सबसे लंबे समय तक पैलिंड्रोमिक बाद का पता लगा सकते हैं।

इस एल्गोरिथम की समय जटिलता 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