(В. Лашин) Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.
Определите в прилагаемом файле подстроку максимальной длины, у которой префикс будет совпадать с суффиксом.
Префиксом и суффиксом подстроки не может являться сама подстрока.
В информатике принято называть префиксом и суффиксом следующие понятия:
- Префикс — начало строки.
- Суффикс — её конец.
Например, у строки "ЕГЭ", префиксы будут "Е", "ЕГ", а суффиксы "Э", "ГЭ"
В ответе запишите число – количество символов в найденной последовательности.
Для выполнения этого задания следует написать программу.
Решение
📌 Результат: 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)
