ค้นหาสตริงย่อย palindromic ที่แตกต่างกันทั้งหมดของสตริงที่กำหนดใน Python

สมมติว่าเรามีสตริงที่มีอักขระ ASCII ตัวพิมพ์เล็ก เราจะต้องค้นหาสตริงย่อยพาลินโดรมที่ต่อเนื่องกันที่ชัดเจนทั้งหมด

ดังนั้น หากอินพุตเป็นเหมือน "bddaaa" ผลลัพธ์จะเป็น [a, aa, aaa, b, d, dd]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• m :=แผนที่ใหม่
• n :=ขนาดของ s
• เมทริกซ์ :=สร้างสองแถวของ n จำนวน 0s
• s :="@" concatenate s concatenate "#"
• สำหรับ j ในช่วง 0 ถึง 1 ให้ทำ
  • อุณหภูมิ :=0
  • เมทริกซ์[j, 0] :=0
  • ผม :=1
  • ในขณะที่ฉัน <=n ทำ
    • ในขณะที่ s[i - temp - 1] เหมือนกับ s[i + j + temp] ให้ทำ
      • อุณหภูมิ :=อุณหภูมิ + 1
    • เมทริกซ์[j, i] :=อุณหภูมิ
    • k :=1
    • ในขณะที่ (เมทริกซ์[j, i - k] ไม่เหมือนกับ temp - k) และ k
    • เมทริกซ์[j,i+k] :=ขั้นต่ำของเมทริกซ์[j, i-k]
    • k :=k + 1
  • อุณหภูมิ :=สูงสุดของอุณหภูมิ - k, 0
  • ผม :=ผม + 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