পাইথনে দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং এর দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং S আছে। আমাদের S তে দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং এর দৈর্ঘ্য খুঁজে বের করতে হবে। আমরা ধরে নিচ্ছি যে S স্ট্রিং এর দৈর্ঘ্য 1000। তাই যদি স্ট্রিংটি "BABAC" হয়, তাহলে দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং হল "BAB" এবং দৈর্ঘ্য 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• স্ট্রিং এর দৈর্ঘ্যের সমান অর্ডারের একটি বর্গ ম্যাট্রিক্স সংজ্ঞায়িত করুন এবং এটি False দিয়ে পূরণ করুন

• প্রধান তির্যক উপাদানগুলিকে সত্য হিসাবে সেট করুন, তাই DP[i, i] =0 থেকে ক্রম পর্যন্ত সমস্ত i-এর জন্য সত্য – 1

• শুরু :=0

• l রেঞ্জ 2 থেকে S + 1

  এর দৈর্ঘ্যের জন্য

  • i এর জন্য 0 থেকে S – l + 1

    এর দৈর্ঘ্যের মধ্যে

    • শেষ :=i + l

    • যদি l =2, তাহলে

      • যদি S[i] =S[শেষ - 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

• রিটার্ন 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