পাইথনে প্রদত্ত স্ট্রিংয়ের সমস্ত স্বতন্ত্র প্যালিনড্রোমিক সাব-স্ট্রিং খুঁজুন

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

সুতরাং, যদি ইনপুটটি "bddaaa" এর মত হয়, তাহলে আউটপুট হবে [a, aa, aaa, b, d, dd]

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

• m :=একটি নতুন মানচিত্র
• n :=s এর আকার
• ম্যাট্রিক্স :=0 সেকেন্ডের n সংখ্যার দুটি সারি তৈরি করুন
• s :="@" concatenate s concatenate "#"
0 থেকে 1 রেঞ্জে j-এর জন্য
• করুন
  • তাপ :=0
  • ম্যাট্রিক্স[j, 0] :=0
  • i :=1
  • যখন i <=n, do
    • যদিও s[i - temp - 1] s[i + j + temp] এর মতো, do
      • temp :=temp + 1
    • ম্যাট্রিক্স[j, i] :=temp
    • k :=1
    • যখন (ম্যাট্রিক্স[j, i - k] temp - k এর মতো নয়) এবং k
    • ম্যাট্রিক্স[j,i+k] :=ন্যূনতম ম্যাট্রিক্স[j, i-k]
    • k :=k + 1
  • temp :=সর্বোচ্চ তাপমাত্রা - k, 0
  • i :=i + k

উদাহরণ

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

def find_substr(s):
   m = dict()
   n = len(s)
   matrix = [[0 for x in range(n+1)] for x in range(2)]
   s = "@" + s + "#"
   for j in range(2):
      temp = 0
      matrix[j][0] = 0
      i = 1
      while i <= n:
         while s[i - temp - 1] == s[i + j + temp]:
            temp += 1
         matrix[j][i] = temp
         k = 1
         while (matrix[j][i - k] != temp - k) and (k < temp):
            matrix[j][i+k] = min(matrix[j][i-k], temp - k)
            k += 1
         temp = max(temp - k, 0)
         i += k
   s = s[1:len(s)-1]
   m[s[0]] = 1
   for i in range(1,n):
      for j in range(2):
         for temp in range(matrix[j][i],0,-1):
            m[s[i - temp - 1 : i - temp - 1 + 2 * temp + j]] = 1
      m[s[i]] = 1
   for i in m:
      print (i)
find_substr("bddaaa")

ইনপুট

bddaaa

আউটপুট

a
aa
b
aaa
d
dd