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

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

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

• স্ট্রিং-এর দৈর্ঘ্যের অর্ডারের একটি স্কয়ার ম্যাট্রিক্স বানান, False দিয়ে ভরা
• মেজর ডায়াগোনাল এলিমেন্টগুলো True করুন, DP[i][i] = True for all i from 0 to order-1
• start := 0
• l কে ২ থেকে S-এর দৈর্ঘ্য + ১ পর্যন্ত লুপ চালান:
  • i কে ০ থেকে 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
• 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