Найти префикс строки максимальной длины, являющийся ретрострокой

def count_repeats(s):
    count = 0
    for i in range(1, len(s)):
        if s[:i] == s[-i:]:
            count += 1
    return count
 
s = input()
n = len(s)
max_len = 0
result = ""
 
for i in range(1, n + 1):
    prefix = s[:i]
    is_retro = True
    repeats_prefix = count_repeats(prefix)
    for j in range(1, i):
        if count_repeats(prefix[:j]) >= repeats_prefix:
            is_retro = False
            break
    if is_retro:
        max_len = i
        result = prefix
 
 
print(result)

def count_repeats(s):
    n = len(s)
    count = 0
    for i in range(1, n):
        if s[:i] == s[-i:]:
            count += 1
    return count
 
s = input()
n = len(s)
max_len = 0
result = ""
 
# Используем кэш для хранения числа повторяемости
repeats_cache = [0] * (n + 1)
 
for i in range(1, n + 1):
    prefix = s[:i]
    # Если число повторяемости для этого префикса ещё не вычислено, вычисляем его
    if repeats_cache[i] == 0:
        repeats_cache[i] = count_repeats(prefix)
    repeats_prefix = repeats_cache[i]
    is_retro = True
    for j in range(1, i):
        # Если число повторяемости для префикса prefix[:j] ещё не вычислено, вычисляем его
        if repeats_cache[j] == 0:
            repeats_cache[j] = count_repeats(s[:j])
        if repeats_cache[j] >= repeats_prefix:
            is_retro = False
            break
    if is_retro:
        max_len = i
        result = prefix
 
print(result)

def compute_prefix_function(s):
    n = len(s)
    p = [0] * n
    for i in range(1, n):
        j = p[i - 1]
        while j > 0 and s[i] != s[j]:
            j = p[j - 1]
        if s[i] == s[j]:
            j += 1
        p[i] = j
    return p
 
def count_repeats_using_prefix_function(s):
    n = len(s)
    p = compute_prefix_function(s)
    repeats = [0] * (n + 1)
    for i in range(n):
        repeats[p[i]] += 1
    for i in range(n - 1, 0, -1):
        repeats[p[i - 1]] += repeats[i]
    for i in range(1, n + 1):
        repeats[i] += 1
    return repeats
 
def find_max_retro_string(s):
    n = len(s)
    p = compute_prefix_function(s)
    repeats = count_repeats_using_prefix_function(s)
    max_len = 0
    result = ""
    for i in range(1, n + 1):
        prefix_repeats = repeats[i]
        is_retro = True
        for j in range(1, i):
            if repeats[j] >= prefix_repeats:
                is_retro = False
                break
        if is_retro:
            max_len = i
            result = s[:i]
    return result
 
s = input().strip()
print(find_max_retro_string(s))

from functools import cache
 
def prefix_func(s):
    p = [0] * len(s)
    for i in range(1, len(s)):
        k = p[i - 1]
        while k > 0 and s[k] != s[i]:
            k = p[k - 1]
        if s[k] == s[i]:
            k += 1
        p[i] = k
    return p
 
@cache
def index_repeat(i):
    if pi[i] > 0:
        return 1 + index_repeat(pi[i]-1)
    return 0
 
s = "aabaabaaabaabaaabaaba"
pi = prefix_func(s)
current_max, max_ind = -1, -1
for i in range(len(s)):
    ind_repeat = index_repeat(i)
    if ind_repeat > current_max:
        current_max, max_ind = ind_repeat, i
print(s[:max_ind+1])