পাইথনে প্যালিনড্রোম করার জন্য ন্যূনতম সংখ্যক অক্ষর যোগ করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, এটিকে প্যালিনড্রোম করতে s-এর পরে ন্যূনতম কতগুলি অক্ষর সন্নিবেশ করতে হবে তা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি s ="mad" এর মত হয়, তাহলে আউটপুট হবে 2, যেহেতু আমরা এটিকে "madam" করতে "am" যোগ করতে পারি।

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

b :=256, m :=10^9 + 7
s :=প্রতিটি i এর জন্য (i এর ASCII) − 97 এর পার্থক্য গ্রহণ করে একটি তালিকা
r :=s-এর শেষ উপাদান, l :=s-এর শেষ উপাদান
n :=s এর আকার
res :=n − 1
p :=b
n − 2 থেকে 0 রেঞ্জে i জন্য, 1 দ্বারা হ্রাস করুন, করুন
- r :=r + s[i] * p, r :=r mod m
- l :=l * b, l :=l + s[i]
- l :=l মোড m
- p :=p * b, p :=p mod m
- যদি l r এর মত হয়, তাহলে
  - res :=i
রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def solve(self, s):
      b = 256
      m = 10 ** 9 + 7
      s = list(ord(i) − 97 for i in s)
      r = l = s[−1]
      n = len(s)
      res = n − 1
      p = b
      for i in range(n − 2, −1, −1):
         r += s[i] * p
         r %= m
         l *= b
         l += s[i]
         l %= m
         p *= b
         p %= m
         if l == r:
            res = i
      return res
ob = Solution()
s = "mad"
print(ob.solve(s))

ইনপুট

"mad"