Задание 24

(В. Лашин) Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.

Определите в прилагаемом файле подстроку максимальной длины, у которой префикс будет совпадать с суффиксом.

Префиксом и суффиксом подстроки не может являться сама подстрока.

В информатике принято называть префиксом и суффиксом следующие понятия:

Префикс — начало строки.
Суффикс — её конец.

Например, у строки "ЕГЭ", префиксы будут "Е", "ЕГ", а суффиксы "Э", "ГЭ"

В ответе запишите число – количество символов в найденной последовательности.

Для выполнения этого задания следует написать программу.

Решение

📌 Результат: 1000002.

s = open("24.txt").read()
n = len(s)

BASE = 911382323
MOD = 10**9 + 7
pow_b = [1] * (n + 1)
pref = [0] * (n + 1)
for i in range(1, n + 1):
    pow_b[i] = pow_b[i - 1] * BASE % MOD
for i, ch in enumerate(s):
    pref[i + 1] = (pref[i] * BASE + ord(ch)) % MOD


def get_hash(left, right):
    return (pref[right] - pref[left] * pow_b[right - left]) % MOD


def has_border(length):
    for i in range(n - length + 1):
        if s[i] != s[i + length - 1]:
            continue
        lo, hi = 1, length - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if (
                get_hash(i, i + mid) == get_hash(i + length - mid, i + length)
                and s[i:i + mid] == s[i + length - mid:i + length]
            ):
                return True
            if s[i:i + mid] == s[i + length - mid:i + length]:
                lo = mid + 1
            else:
                hi = mid - 1
    return False


lo, hi = 1, n
while lo < hi:
    mid = (lo + hi + 1) // 2
    if has_border(mid):
        lo = mid
    else:
        hi = mid - 1

print(lo)

Скачать файл