सबसे लंबा पैलिंड्रोमिक सबस्ट्रिंग

किसी दिए गए स्ट्रिंग में, हमें एक सबस्ट्रिंग ढूंढनी है, जो एक पैलिंड्रोम है और यह सबसे लंबी है।

सबसे लंबी पैलिंड्रोमिक सबस्ट्रिंग प्राप्त करने के लिए, हमें कई उप-समस्याओं को हल करना होगा, कुछ उप-समस्याएं अतिव्यापी हैं। उन्हें कई बार हल करने की आवश्यकता होती है। उस कारण से, डायनेमिक प्रोग्रामिंग मददगार है। तालिका का उपयोग करके, हम पिछली उप-समस्याओं के परिणामों को संग्रहीत कर सकते हैं, और बस उनका उपयोग आगे के परिणाम उत्पन्न करने के लिए कर सकते हैं।

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

Input:
A String. Say “thisispalapsiti”
Output:
The palindrome substring and the length of the palindrome.
Longest palindrome substring is: ispalapsi
Length is: 9

एल्गोरिदम

findLongPalSubstr(str)

इनपुट - मुख्य स्ट्रिंग।

आउटपुट - सबसे लंबा पैलिंड्रोमिक सबस्ट्रिंग और इसकी लंबाई।

Begin
   n := length of the given string
   create a n x n table named palTab to store true or false value
   fill patTab with false values
   maxLen := 1

   for i := 0 to n-1, do
      patTab[i, i] = true       //as it is palindrome of length 1
   done

   start := 0
   for i := 0 to n-2, do
      if str[i] = str[i-1], then
         palTab[i, i+1] := true
         start := i
         maxLen := 2
   done

   for k := 3 to n, do
      for i := 0 to n-k, do
         j := i + k – 1
         if palTab[i+1, j-1] and str[i] = str[j], then
            palTab[i, j] := true
            if k > maxLen, then
               start := i
               maxLen := k
      done
   done
   display substring from start to maxLen from str, and return maxLen
 End

उदाहरण

#include<iostream>
using namespace std;

int findLongPalSubstr(string str) {
   int n = str.size();        // get length of input string
 
   bool palCheckTab[n][n];    //true when substring from i to j is palindrome
   
   for(int i = 0; i<n; i++)
      for(int j = 0; j<n; j++)
         palCheckTab[i][j] = false;      //initially set all values to false
 
   int maxLength = 1;
   
   for (int i = 0; i < n; ++i)
      palCheckTab[i][i] = true;       //as all substring of length 1 is palindrome
 
   int start = 0;
   for (int i = 0; i < n-1; ++i) {
      if (str[i] == str[i+1]) {      //for two character substring both characters are equal
         palCheckTab[i][i+1] = true;
         start = i;
         maxLength = 2;
      }
   }
 
   for (int k = 3; k <= n; ++k) {       //for substrings with length 3 to n
      for (int i = 0; i < n-k+1 ; ++i) {
         int j = i + k - 1;
         if (palCheckTab[i+1][j-1] && str[i] == str[j]) {    //if (i,j) and (i+1, j-1) are same, then check palindrome
            palCheckTab[i][j] = true;
            if (k > maxLength) {
               start = i;
               maxLength = k;
            }
         }
      }
   }
   cout << "Longest palindrome substring is: " << str.substr(start, maxLength) << endl;
   return maxLength; // return length
}
 
int main() {
   char str[] = "thisispalapsiti";
   cout << "Length is: "<< findLongPalSubstr(str);
}

आउटपुट

Longest palindrome substring is: ispalapsi
Length is: 9