def manacher(s):
"""Manacher's Algorithm to find all palindromic substrings in linear time."""
s = '#' + '#'.join(s) + '#'
n = len(s)
p = [0] * n
c = 0
r = 0
for i in range(n):
mirror = 2 * c - i
if i < r:
p[i] = min(r - i, p[mirror])
while i + p[i] + 1 < n and i - p[i] - 1 >= 0 and s[i + p[i] + 1] == s[i - p[i] - 1]:
p[i] += 1
if i + p[i] > r:
c = i
r = i + p[i]
return s, p
def find_max_palindrome_occurrence_value(s):
original_s = s
s, p = manacher(s)
n = len(p)
# To store the count of each palindrome
palindrome_count = {}
for i in range(n):
length = p[i]
if length > 0:
start = (i - length) // 2
for l in range(1, length + 1):
pal_sub = original_s[start:start + l]
if pal_sub in palindrome_count:
palindrome_count[pal_sub] += 1
else:
palindrome_count[pal_sub] = 1
start -= 1
max_occurrence_value = 0
for pal, count in palindrome_count.items():
occurrence_value = len(pal) * count
if occurrence_value > max_occurrence_value:
max_occurrence_value = occurrence_value
return max_occurrence_value
# Read input from file
with open('palindrome.in', 'r') as file:
s = file.read().strip()
# Calculate the maximum occurrence value of palindromic substrings
result = find_max_palindrome_occurrence_value(s)
# Write output to file
with open('palindrome.out', 'w') as file:
file.write(str(result) + '\n')
