สมมติว่าเรามีสตริง str ขอบ (Border) ของสตริงคือ substring ที่เป็น proper prefix และ suffix พร้อมกัน เช่น 'ab' เป็น border ของ 'ababab' ขอบที่เป็นพาลินโดรม (Palindrome Border) คือขอบที่ตัวมันเองเป็นพาลินโดรม กำหนด f(str) = จำนวน palindrome borders ของ str ต้องหาผลรวม f(str_k) สำหรับทุก substring str_k ที่ไม่ว่าง modulo 10^9+7
ตัวอย่าง str = 'pqpqp' ผลลัพธ์ = 5 มี substring 15 ตัว แต่มี 4 ตัวที่มี palindromic borders: pqp (1), pqpqp (2), qpq (1), pqp (1) รวม = 5
ขั้นตอนการแก้ปัญหา
- ใช้ Manacher-like Algorithm ขยาย palindrome จากศูนย์กลาง
- แยกคำนวณสำหรับ palindrome ความยาวคี่ (odd) และคู่ (even)
- ใช้ Dictionary นับความถี่ของแต่ละ palindrome substring
- สำหรับแต่ละ palindrome ที่มีความถี่ f เพิ่ม f*(f-1)/2 เข้าคำตอบ
- Modulo 1,000,000,007
ตัวอย่างโค้ด
def palindrome_calculator(input_dict):
ans = 0
for item1, item2 in input_dict.items():
ans += item2 * (item2 - 1) // 2
return ans
def str_check(string):
t_str = string[0]
for s in string:
if s != t_str:
return False
return True
def string_res(string):
ans = 0
for i in range(2, len(string) + 1):
ans += i * (i - 1) // 2
ans %= 1000000007
return ans
def solve(string):
if str_check(string):
return string_res(string)
ans = 0
odd_list = [[], {}, 1]
for s in string:
if s not in odd_list[1]:
odd_list[1][s] = 0
odd_list[1][s] += 1
for i in range(len(string)):
odd_list[0].append(i)
ans += palindrome_calculator(odd_list[1])
even_list = [[], {}, 1]
for i in range(len(string) - 1):
if string[i] == string[i + 1]:
even_list[0].append(i)
tmp = string[i:i + 2]
if tmp not in even_list[1]:
even_list[1][tmp] = 0
even_list[1][tmp] += 1
ans += palindrome_calculator(even_list[1])
for val in range(3, len(string)):
if val % 2 == 0:
wt = even_list
else:
wt = odd_list
new_t = [[], {}, val]
for index in wt[0]:
if index - 1 >= 0 and index + val - 2 < len(string) and string[index - 1] == string[index + val - 2]:
new_t[0].append(index - 1)
tmp = string[index - 1 : index - 1 + val]
if tmp not in new_t[1]:
new_t[1][tmp] = 0
new_t[1][tmp] += 1
ans += palindrome_calculator(new_t[1])
ans %= 1000000007
if val % 2 == 0:
even_list = new_t
else:
odd_list = new_t
return ans
print(solve('pqpqp'))
อินพุต
'pqpqp'
เอาต์พุต
5
