Cho chuỗi text. Tìm k lớn nhất sao cho tồn tại a[1]..a[k] (chuỗi không rỗng) thỏa: (1) nối a[1]+..+a[k] = text, (2) a[i] = a[k+1-i] ∀i. Đây là phân hoạch palindrome chunked.
Ví dụ: text = "antaprezatepzapreanta" → output = 11 (a|nt|a|pre|za|tpe|za|pre|a|nt|a).
Giải thuật (Two-pointer greedy)
- Dùng 2 con trỏ i (từ trái), j (từ phải). ic, jc đánh dấu ranh giới chunk hiện tại.
- Khi text[ic:i] == text[j:jc]: tìm thấy cặp chunk đối xứng → counter += 2, cập nhật ic=i, jc=j.
- Tăng i, giảm j. Cuối cùng nếu ic != jc → còn chunk giữa → counter += 1.
Code Python
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)) # 11
Đầu vào / Đầu ra
Input: "antaprezatepzapreanta"
Output: 11