पायथन में दिए गए स्ट्रिंग के सभी विशिष्ट पैलिंड्रोमिक उप-स्ट्रिंग खोजें

मान लीजिए कि हमारे पास ASCII वर्णों के साथ एक स्ट्रिंग है, हमें इसके सभी अलग-अलग निरंतर पैलिंड्रोमिक सबस्ट्रिंग खोजने होंगे।

इसलिए, यदि इनपुट "bddaaa" जैसा है, तो आउटपुट [a, aa, aaa, b, d, dd]

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

• m :=एक नया नक्शा
• n :=आकार का
• मैट्रिक्स :=n संख्या 0s की दो पंक्तियाँ बनाएं
• s :="@" concatenate s concatenate "#"
• जे के लिए 0 से 1 की सीमा में, करें
  • अस्थायी:=0
  • मैट्रिक्स[जे, 0] :=0
  • मैं :=1
  • जबकि मैं <=n, करते हैं
    • जबकि s[i - temp - 1] s[i + j + temp] के समान है, do
      • अस्थायी:=अस्थायी + 1
    • मैट्रिक्स[जे, आई] :=अस्थायी
    • k :=1
    • जबकि (मैट्रिक्स[j, i - k] अस्थायी - k के समान नहीं है) और k
    • मैट्रिक्स[j,i+k] :=न्यूनतम मैट्रिक्स[j, i-k]
    • k :=k + 1
  • अस्थायी:=अधिकतम तापमान - 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