পাইথনে লองেস্ট প্যালিনড্রোমিক সাবস্ট্রিং (Longest Palindromic Substring)

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

সমাধানের ধাপসমূহ:

• স্ট্রিং দৈর্ঘ্যের সমান অর্ডারের একটি স্কয়ার ম্যাট্রিক্স ডিফাইন করুন এবং False দিয়ে পূরণ করুন।
• মেজর ডায়াগোনাল এলিমেন্টগুলো True সেট করুন: DP[i, i] = True for all i from 0 to order-1
• start := 0
• for l in range 2 to length of S + 1
  • for i in range 0 to length of S - l + 1
    • end := i + l
    • if l = 2, then
      • if S[i] = S[end - 1], then DP[i, end - 1] = True, max_len := l, and start := i
    • otherwise
      • if S[i] = S[end - 1] and DP[i + 1, end - 2], then DP[i, end - 1] = True, max_len := l, and 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"