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

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

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

• स्ट्रिंग की लंबाई के समान क्रम के एक वर्ग मैट्रिक्स को परिभाषित करें, और इसे गलत से भरें
• प्रमुख विकर्ण तत्वों को सत्य के रूप में सेट करें, इसलिए DP[i, i] =0 से क्रम -1 तक सभी के लिए सही है - 1
• शुरू करें:=0
• एल के लिए रेंज 2 से लेकर एस + 1 की लंबाई तक
  • i के लिए 0 से S की लंबाई तक - l + 1
    • अंत :=i + l
    • अगर एल =2, तो
      • अगर एस[i] =एस[अंत -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
• इंडेक्स स्टार्ट से स्टार्ट + मैक्स_लेन का सबस्ट्रिंग लौटाएं

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

बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -

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"