पायथन में सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग की लंबाई खोजने का कार्यक्रम

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

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

• स्ट्रिंग की लंबाई के समान क्रम के एक वर्ग मैट्रिक्स को परिभाषित करें, और इसे गलत से भरें

• प्रमुख विकर्ण तत्वों को सत्य के रूप में सेट करें, इसलिए DP[i, i] =0 से क्रम तक सभी i के लिए सही – 1

• प्रारंभ:=0

• l के लिए 2 से लेकर S + 1 की लंबाई तक

  • मैं के लिए 0 से लेकर S - l + 1 तक की लंबाई के लिए

    • अंत:=मैं + एल

    • अगर एल =2, तो

      • अगर एस [i] =एस [अंत -1], तो

        • DP[i, end - 1] =True, max_len :=l, और start :=i

    • अन्यथा

      • अगर एस [i] =एस [अंत -1] और डीपी [i + 1, अंत - 2], तो

        • DP[i, end - 1] =True, max_len :=l, और start :=i

• वापसी max_len

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

उदाहरण

class Solution(object):
   def solve(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 max_length

ob = Solution()
print(ob.solve('BABAC'))

इनपुट

"ABBABBC"

आउटपुट

5