पायथन का उपयोग करके सबसे लंबे पैलिंड्रोमिक बाद की लंबाई का पता लगाने का कार्यक्रम

मान लीजिए, हमें एक स्ट्रिंग दी गई है। हमें एक पैलिंड्रोमिक अनुक्रम का पता लगाना है जो सम लंबाई का हो और जिसमें बीच को छोड़कर लगातार दो समान वर्ण न हों। हमें इस प्रकार के सबस्ट्रिंग की लंबाई को आउटपुट के रूप में वापस करना होगा।

इसलिए, यदि इनपुट s ='efeffe' जैसा है, तो आउटपुट 4

. होगा

आउटपुट 4 है क्योंकि केवल एक पैलिंड्रोमिक क्रम है जो सम लंबाई का है। स्ट्रिंग 'इफ़े' है जिसकी लंबाई 4 है।

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

n :=s का आकार
dp :=एक n x n 2d सरणी जहां प्रत्येक आइटम फॉर्म में एक जोड़ी है (0, रिक्त स्ट्रिंग)
n-1 से -1 की श्रेणी में i के लिए, 1 से घटाएं, करें
- i+1 से n की श्रेणी में j के लिए, करें
  - अगर s[i] s[j] के समान है और dp[i+1, j-1] की स्ट्रिंग s[i] नहीं है, तो
    - dp[i, j] :=एक जोड़ी बनाएं (dp[i+1, j-1] + 2, s[i] का पहला तत्व)
  - अन्यथा,
    - dp[i, j] :=इनमें से चुनें (dp[i+1, j], dp[i, j-1], dp[i+1,j-1]) जिसके लिए जोड़ी का पहला तत्व अधिकतम है
  - dp[0, n-1]
    . पर संग्रहीत जोड़ी का पहला तत्व लौटाएं

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

उदाहरण

def solve(s):
   n = len(s)
   dp = [[(0, '')]*n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(i+1, n):
         if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
            dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
         else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
   return dp[0][n-1][0]
print(solve('efeffe'))

इनपुट

'efeffe'