Повышенный / Высокий (1 балл) Время: 5-10 мин Python 3 open('24.txt') replace() + split() Метод сплитов по символу Однопроходная динамика O(N) Все задачи №24 в каталоге

Задание №24. Анализ символьных строк (до 5 000 000 символов)

Тема: Поиск максимальных цепочек, метод маркеров и сплитов, линейная динамика и скользящее окно

В текстовом файле записана гигантская строка (до 5 000 000 знаков). Задача — найти максимальную длину непрерывной подстроки, удовлетворяющей условию: цепочки пар (Согласная+Гласная), не более K определенных символов, чередующиеся последовательности или арифметические выражения.

1. Метод 1: Маркеры и сплиты (для цепочек пар / троек):

Если требуется найти самую длинную цепочку пар вида Согласная + Гласная (например, из букв C, D, F и A, O):

Заменяем все валидные пары на звёздочку *:
```
for c in 'CDF':
    for v in 'AO':
        s = s.replace(c + v, '*')
```
Все остальные оставшиеся символы заменяем на пробелы:
```
for ch in 'CDFAO':
    s = s.replace(ch, ' ')
```
Разбиваем по пробелам и берем максимум: max_len = max(len(chunk) for chunk in s.split()).

2. Метод 2: Сплиты по целевому символу (Не более $K$ букв 'T'):

Окно, содержащее ровно $K$ букв 'T', состоит ровно из $K+1$ соседних фрагментов массива s.split('T') плюс сами $K$ букв 'T':

parts = s.split('T')
max_len = 0
for i in range(len(parts) - K):
    # Суммируем длины K+1 кусков и добавляем K разделителей 'T':
    current_window = sum(len(parts[j]) for j in range(i, i + K + 1)) + K
    max_len = max(max_len, current_window)

3. Метод 3: Универсальная однопроходная динамика $O(N)$:

cur_len = 1
max_len = 1
for i in range(1, len(s)):
    if (s[i] in vowels) != (s[i-1] in vowels): # Чередование
        cur_len += 1
        max_len = max(max_len, cur_len)
    else:
        cur_len = 1

Разновидности и прототипы задания на экзамене

Тип 1: Метод маркеров и сплитов replace() + split()

Замена целевых пар/троек на маркер '*' с последующей заменой остальных букв на пробелы и вычислением max(len(chunk) for chunk in s.split()).

Тип 2: Не более K вхождений определенного символа (Хит ЕГЭ)

Сплит по ключевой букве parts = s.split('A') и суммирование длин соседних K+1 блоков плюс K.

Тип 3: Чередующиеся символы и однопроходная динамика O(N)

Подстроки, где никакие две гласные или две согласные не стоят рядом. Линейный проход со счетчиком cur_len.

Тип 4: Арифметические выражения и валидные цепочки

Поиск корректных выражений вида '12+45*3' без ведущих нулей и подряд идущих знаков операций.

Боевой шаблон решения на Python

Запустить код в онлайн-песочнице

Боевой шаблон решения на Python

s = open("24.txt").readline().strip()

k = 150
parts = s.split("Y")
best = 0
for i in range(len(parts) - k):
    length = k
    for j in range(i, i + k + 1):
        length += len(parts[j])
    best = max(best, length)

print(best)

Задача из базы, которую решает этот код Открыть в песочнице

Типичные ошибки

✕ Не так

Ошибка: Вложенные циклы s[i:j] с квадратичной сложностью O(N^2)

Строка из 2 000 000 символов потребует 4 триллиона операций и зависнет намертво!

✓ Так

Правильно: Использовать строго линейные алгоритмы O(N) (метод сплитов или 1 цикл).

✕ Не так

Ошибка: replace('CA', '*') без замены остальных букв на пробелы

Если буквы останутся в строке, len(chunk) посчитает их вместе со звёздочками!

✓ Так

Правильно: Все символы алфавита, не превратившиеся в '*', заменять на пробелы.

ГРОБ

ГРОБ №24: Цепочка пар, начинающаяся или заканчивающаяся одиночным символом

В вопросе задачи: 'максимальная длина в символах'. Цепочка может иметь вид (Гласная + пары + Согласная).

Как обойти

После нахождения максимальной цепочки звёздочек проверьте соседние символы слева и справа от найденного блока в исходной строке.

Лайфхаки на экзамене

Метод s.split('T') работает мгновенно (за 0.05 секунды) даже на 5-мегабайтных файлах!
Для подсчета длины в парах умножайте на 2 только если в задаче спрашивают количество символов, а не пар.

Банк реальных задач №24 Открыть в тренажере СмартКИМ