Задание 24: поиск подстрок в большом файле
Коротко
В задании 24 дан файл с длинной строкой. Обычно нужно найти длину самой длинной подстроки с заданным свойством: без двух одинаковых соседних символов, из определённых букв, содержащей не больше k нужных символов. Решение — один проход с текущей длиной: если очередной символ продолжает подходящую цепочку, длина растёт, иначе цепочка начинается заново. Для «не больше k» применяют два указателя.
Шаблон: нет двух одинаковых соседних
s = open('24.txt').readline().strip()
best = cur = 1
for i in range(1, len(s)):
cur = cur + 1 if s[i] != s[i - 1] else 1
best = max(best, cur)
print(best)
Два указателя
Для «подстрока, где буква X встречается не больше k раз»: двигайте правый край, а когда X стало больше k — сдвигайте левый край.
Регулярные выражения
re.findall с подходящим шаблоном ищет все цепочки; затем берут максимум длин.
Типичные ошибки
- Начинают новую цепочку с 0, а не с 1.
- Забывают strip() и считают символ перевода строки.
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 24
Пример 1 из 2
Строка ABBABABACCA. Длина самой длинной подстроки без двух одинаковых соседних символов?
- Разбор
- После BB идёт BABABAC — 7 символов; программа даёт 7.
- Ответ
- 7
Пример 2 из 2
Зачем strip() при чтении строки?
- Разбор
- Убирает символ перевода строки в конце.
- Ответ
- Чтобы не считать \n
Мини-тест: 5 вопросов
- Вопрос 1 из 5
С какого значения начинается новая цепочка?
Показать ответ
Ответ: С 1.
Текущий символ.
- Вопрос 2 из 5
Метод для двух указателей?
Показать ответ
Ответ: Сдвигать левый край при нарушении условия.
Окно.
- Вопрос 3 из 5
Как прочитать строку из файла?
Показать ответ
Ответ: open(...).readline().strip().
Одна строка.
- Вопрос 4 из 5
Модуль регулярных выражений?
Показать ответ
Ответ: re.
re.findall.
- Вопрос 5 из 5
Сколько проходов нужно в простом случае?
Показать ответ
Ответ: Один.
Линейное время.
Проверьте всё задание 24, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти