Submission #998536

#	Time	Username	Problem	Language	Result	Execution time	Memory
998536		Ibrohim0704	Palindromes (APIO14_palindrome)	Pypy 3	0 / 100	58 ms	20280 KiB

palindrome

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')

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27