Cho chuỗi str. Border của chuỗi là substring vừa là proper prefix vừa là suffix. Border palindrome là border đồng thời là palindrome. Với mỗi substring str_k của str, tính f(str_k) = số border palindrome. Tìm tổng f(str_k) cho tất cả substring không rỗng, modulo 10⁹+7.
Ví dụ: 'pqpqp' → 15 substring, 4 substring có border palindrome, tổng = 5.
Thuật toán Manacher mở rộng
Sử dụng kỹ thuật mở rộng palindrome theo độ dài chẵn/lẻ (odd/even length palindromes), đếm tần suất mỗi palindrome, áp dụng công thức tổ hợp C(freq, 2) cho mỗi palindrome để đếm cặp border. Xử lý riêng trường hợp chuỗi toàn cùng một ký tự.
Ví dụ mã nguồn
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')) # 5
Đầu vào / Đầu ra
Input: 'pqpqp'
Output: 5