สมมติว่าเรามีข้อความ เราต้องหา k ที่ใหญ่ที่สุดเท่าที่จะเป็นไปได้ซึ่งมีอยู่ a[1], a[2], ..., a[k] เช่นนั้น:แต่ละ a[i] เป็นสตริงที่ไม่ว่างเปล่า และการต่อกัน a[1] + a[2] + ... + a[k] เท่ากับข้อความที่กำหนด สำหรับ i ทั้งหมดในช่วง 1 ถึง k, a[i] =a[{k+1 - i}].
ดังนั้น หากอินพุตเป็นเหมือน text ="antaprezatepzapreanta" ผลลัพธ์จะเป็น 11 เพราะเราสามารถแยกออกเป็น "a|nt|a|pre|za|tpe|za|pre|a|nt|a" ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เคาน์เตอร์ :=0
-
ผม :=1, j :=ขนาดของข้อความ - 1
-
ic :=0, jc :=ขนาดของข้อความ
-
ในขณะที่ฉัน <=j ทำ
-
หากสตริงย่อยของข้อความ[จากดัชนี ic ถึง i-1] เหมือนกับสตริงย่อยของข้อความ[จากดัชนี j ถึง jc-1] ดังนั้น
-
ตัวนับ :=ตัวนับ + 2
-
ไอซี :=ฉัน
-
jc :=เจ
-
-
ผม :=ผม + 1
-
เจ :=เจ - 1
-
-
ถ้า ic ไม่เหมือนกับ jc แล้ว
-
เคาน์เตอร์ :=เคาน์เตอร์ + 1
-
-
เคาน์เตอร์คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(text):
counter = 0
i, j = 1, len(text) - 1
ic, jc = 0, len(text)
while i <= j:
if text[ic:i] == text[j:jc]:
counter += 2
ic = i
jc = j
i += 1
j -= 1
if ic != jc:
counter += 1
return counter
text = "antaprezatepzapreanta"
print(solve(text)) อินพุต
[3,4,5,2,1,7,3,4,7], 3
ผลลัพธ์
11
