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

मान लीजिए हमारे पास एक स्ट्रिंग S है। हमें S में सबसे लंबा पालिंड्रोमिक सबस्ट्रिंग ढूंढना है। हम मान रहे हैं कि स्ट्रिंग S की लंबाई 1000 है। इसलिए यदि स्ट्रिंग "BABAC" है, तो सबसे लंबा पालिंड्रोमिक सबस्ट्रिंग "BAB" है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• स्ट्रिंग की लंबाई के समान क्रम का एक वर्ग मैट्रिक्स परिभाषित करें, और इसे False से भरें
• मेजर डायगोनल एलिमेंट्स को true पर सेट करें, इसलिए DP[i, i] = True सभी i के लिए 0 से order - 1 तक
• start := 0
• l को 2 से S की लंबाई + 1 तक की रेंज में लिए लिए
  • i को 0 से S की लंबाई - l + 1 तक की रेंज में लिए
    • end := i + l
    • यदि l = 2, तो
      • यदि S[i] = S[end - 1], तो
        • DP[i, end - 1] = True, max_len := l, और start := i
    • अन्यथा
      • यदि S[i] = S[end - 1] और DP[i + 1, end - 2], तो
        • DP[i, end - 1] = True, max_len := l, और start := i
• इंडेक्स start से start + max_len तक का सबस्ट्रिंग लौटाएं

उदाहरण (पायथन)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

class Solution(object):
    def longestPalindrome(self, s):
        dp = [[False for i in range(len(s))] for i in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = True
        max_length = 1
        start = 0
        for l in range(2, len(s)+1):
            for i in range(len(s)-l+1):
                end = i+l
                if l==2:
                    if s[i] == s[end-1]:
                        dp[i][end-1]=True
                        max_length = l
                        start = i
                else:
                    if s[i] == s[end-1] and dp[i+1][end-2]:
                        dp[i][end-1]=True
                        max_length = l
                        start = i
        return s[start:start+max_length]

ob1 = Solution()
print(ob1.longestPalindrome("ABBABBC"))

इनपुट

"ABBABBC"

आउटपुट

"BBABB"