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

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

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

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

इनपुट: एक स्ट्रिंग। मान लें "thisispalapsiti"
आउटपुट: पैलिंड्रोम सबस्ट्रिंग और उसकी लंबाई।
सबसे लंबा पैलिंड्रोम सबस्ट्रिंग है: ispalapsi
लंबाई है: 9

एल्गोरिदम

findLongPalSubstr(str)

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

शुरुआत
    n := दी गई स्ट्रिंग की लंबाई
    palTab नामक n x n टेबल बनाएं जो true/false मान स्टोर करे
    palTab को false मानों से भरें
    maxLen := 1
    i := 0 से n-1 तक, करें
        palTab[i, i] = true
        // क्योंकि यह लंबाई 1 का पैलिंड्रोम है
    पूर्ण
    start := 0
    i := 0 से n-2 तक, करें
        यदि str[i] = str[i+1], तो
            palTab[i, i+1] := true
            start := i
            maxLen := 2
        पूर्ण
    पूर्ण
    k := 3 से n तक, करें
        i := 0 से n-k तक, करें
            j := i + k - 1
            यदि palTab[i+1, j-1] और str[i] = str[j], तो
                palTab[i, j] := true
                यदि k > maxLen, तो
                    start := i
                    maxLen := k
            पूर्ण
        पूर्ण
    पूर्ण
    str से start से maxLen तक सबस्ट्रिंग प्रदर्शित करें, और maxLen वापस करें
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int findLongPalSubstr(string str) {
    int n = str.size();
    bool palCheckTab[n][n];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            palCheckTab[i][j] = false;
    
    int maxLength = 1;
    for (int i = 0; i < n; ++i)
        palCheckTab[i][i] = true;
    
    int start = 0;
    for (int i = 0; i < n-1; ++i) {
        if (str[i] == str[i+1]) {
            palCheckTab[i][i+1] = true;
            start = i;
            maxLength = 2;
        }
    }
    
    for (int k = 3; k <= n; ++k) {
        for (int i = 0; i < n-k+1; ++i) {
            int j = i + k - 1;
            if (palCheckTab[i+1][j-1] && str[i] == str[j]) {
                palCheckTab[i][j] = true;
                if (k > maxLength) {
                    start = i;
                    maxLength = k;
                }
            }
        }
    }
    
    cout << "Longest palindrome substring is: " << str.substr(start, maxLength) << endl;
    return maxLength;
}

int main() {
    char str[] = "thisispalapsiti";
    cout << "Length is: " << findLongPalSubstr(str);
}

आउटपुट

Longest palindrome substring is: ispalapsi
Length is: 9