Tìm tất cả các chuỗi con palindromic riêng biệt của một chuỗi đã cho bằng Python

Giả sử chúng ta có một chuỗi với các ký tự ASCII viết thường, chúng ta phải tìm tất cả các chuỗi con palindromic liên tục riêng biệt của nó.

Vì vậy, nếu đầu vào là "bddaaa", thì đầu ra sẽ là [a, aa, aaa, b, d, dd]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=một bản đồ mới
• n:=kích thước của s
• ma trận:=tạo thành hai hàng gồm n số 0
• s:="@" concatenate s concatenate "#"
• đối với j trong phạm vi từ 0 đến 1, thực hiện
  • tạm thời:=0
  • ma trận [j, 0]:=0
  • i:=1
  • while i <=n, do
    • while s [i - temp - 1] giống với s [i + j + temp], do
      • temp:=temp + 1
    • ma trận [j, i]:=temp
    • k:=1
    • while (ma trận [j, i - k] không giống với temp - k) và k
    • ma trận [j, i + k]:=tối thiểu của ma trận [j, i-k]
    • k:=k + 1
  • temp:=tối đa của temp - k, 0
  • i:=i + k

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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")

Đầu vào

bddaaa

Đầu ra

a
aa
b
aaa
d
dd