मैनाचर का एल्गोरिदम

एक स्ट्रिंग से सबसे लंबा पालिंड्रोमिक सबस्ट्रिंग ढूंढने के लिए, हम मैनाचर के एल्गोरिदम का उपयोग कर सकते हैं। प्रत्येक कैरेक्टर को चुनकर, हम बाएं और दाएं पॉइंटर का उपयोग करके जांचने का प्रयास करेंगे कि क्या कोई पालिंड्रोम है। जानकारी स्टोर करने के लिए एक और ऐरे है, उस जानकारी से हम आसानी से ढूंढ सकते हैं कि पालिंड्रोम कितना लंबा है। प्रत्येक कैरेक्टर के लिए, ऐरे जानकारी स्टोर करेगा। पूरे स्ट्रिंग को ट्रैवर्स करने के बाद, हम बनाए गए ऐरे से सबसे लंबा पालिंड्रोमिक सबसीक्वेंस ढूंढ सकते हैं।

इस एल्गोरिदम की समय जटिलता O(n) है।

इनपुट और आउटपुट

इनपुट: स्ट्रिंग: "levelup" आउटपुट: सबसे लंबा पालिंड्रोम है: 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 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]; maxCenterIndex = 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