Giả sử chúng ta có một chuỗi; chúng ta phải tìm tất cả các chuỗi con palindromic từ chuỗi đó. Ở đây aa và aa được coi là hai chuỗi con, không phải là một.
Vì vậy, nếu đầu vào giống như redivider, thì đầu ra sẽ là ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider' , 'i', 'd', 'e', 'r']
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- v:=một danh sách mới
- pos:=0.0
- while pos
- rad:=pos - (pos là số nguyên)
- while (pos + rad)
=0 and (s [integer of (pos - rad)] giống như s [integer of (pos + rad)]), do - chèn s [từ số nguyên chỉ số của (pos - rad) đến số nguyên của (pos + rad + 1)] vào cuối v
- rad:=rad + 1
- pos:=pos + 0,5
Mã mẫu
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def get_all_pal_sub(s): v = [] pos = 0.0 while pos < len(s): rad = pos - int(pos) while ((pos + rad) < len(s) and (pos - rad) >= 0 and (s[int(pos - rad)] == s[int(pos + rad)])): v.append(s[int(pos - rad): int(pos + rad + 1)]) rad += 1 pos += 0.5 return v v = get_all_pal_sub("redivider") print(len(v)) print(v)
Đầu vào
"redivider"
Đầu ra
13 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']