(В. Лашин) Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.
Определите в прилагаемом файле подстроку максимальной длины, у которой префикс будет совпадать с суффиксом.
Префиксом и суффиксом подстроки не может являться сама подстрока.
В информатике принято называть префиксом и суффиксом следующие понятия:
- Префикс — начало строки.
- Суффикс — её конец.
Например, у строки «ЕГЭ», префиксы будут «Е», «ЕГ», а суффиксы «Э», «ГЭ».
В ответе запишите число – количество символов в найденной последовательности.
Для выполнения этого задания следует написать программу.
Решение
Множество
🔹 Шаг 1. Читаем файл в строку, собираем множество всех символов строки и…
s = open("24.txt").read()
alf = set(s)
res = []
📌 Читаем файл в строку, собираем множество всех символов строки и создаём список для кандидатов на ответ.
🔹 Шаг 2. Для каждого символа находим его первое и последнее вхождение в строке
for b in alf:
l = s.index(b)
r = s.rindex(b)
sd = 0
📌 Для каждого символа находим его первое и последнее вхождение в строке — это будущие концы искомой подстроки.
🔹 Шаг 3. Сравниваем символы сразу после левого и правого концов
while r + sd + 1 < len(s) and s[l + sd + 1] == s[r + sd + 1]:
sd += 1
📌 Сравниваем символы сразу после левого и правого концов: пока они совпадают, увеличиваем длину общей границы префикса и суффикса.
🔹 Шаг 4. Записываем длину подстроки от первого до последнего вхождения плюс…
res.append(r - l + 1 + sd)
📌 Записываем длину подстроки от первого до последнего вхождения плюс совпадающий хвост и переходим к следующему символу.
🔹 Шаг 5. Жми RUN
print(max(res))
📌 Жми RUN — в выводе будет максимальная длина подстроки с совпадающим префиксом и суффиксом (1000002).
✅ Ответ: 1000002
🔹 Полный код
s = open("24.txt").read()
alf = set(s)
res = []
for b in alf:
l = s.index(b)
r = s.rindex(b)
sd = 0
while r + sd + 1 < len(s) and s[l + sd + 1] == s[r + sd + 1]:
sd += 1
res.append(r - l + 1 + sd)
print(max(res))
