สมมติว่าเรามีสตริง เราต้องหาสตริงย่อยพาลินโดรมทั้งหมดจากสตริงนั้น ในที่นี้ aa และ aa ถือเป็นสองสตริงย่อย ไม่ใช่หนึ่งสตริง
ดังนั้น หากอินพุตเป็นเหมือนตัวแบ่ง ผลลัพธ์จะเป็น ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider' , 'i', 'd', 'e', 'r']
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- v :=รายการใหม่
- ตำแหน่ง :=0.0
- ในขณะที่ pos <ขนาดของ s ทำ
- rad :=pos - (pos เป็นจำนวนเต็ม)
- ในขณะที่ (pos + rad) <ขนาดของ s และ (pos - rad)>=0 และ (s[integer of (pos - rad)] เท่ากับ s[integer of (pos + rad)]) ให้ทำ
- แทรก s[จากจำนวนเต็มดัชนีของ (pos - rad) เป็นจำนวนเต็มของ (pos + rad + 1)] ที่ส่วนท้ายของ v
- ราด :=ราด + 1
- pos :=pos + 0.5
- รีเทิร์นวี
โค้ดตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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) อินพุต
"redivider"
ผลลัพธ์
13 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']
