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

Задание №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

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

# === Универсальный боевой шаблон Задания №24 на Python ===

# 1. Читаем файл целиком (open('24.txt')):
with open('24.txt') as f:
    s = f.read().strip()

# --- ВАРИАНТ А: Метод маркеров (цепочка пар Согласная + Гласная) ---
s_pairs = s
for c in "CDF":
    for v in "AO":
        s_pairs = s_pairs.replace(c + v, '*')

for ch in "CDFAO":
    s_pairs = s_pairs.replace(ch, ' ')

max_pairs = max(len(chunk) for chunk in s_pairs.split())
print("Максимальная длина цепочки пар:", max_pairs)

# --- ВАРИАНТ Б: Не более K букв 'T' в подстроке (например, K = 100) ---
k = 100
parts = s.split('T')
max_t_len = 0
for i in range(len(parts) - k):
    win = sum(len(parts[j]) for j in range(i, i + k + 1)) + k
    if win > max_t_len:
        max_t_len = win

print(f"Максимальная длина с не более {k} букв T:", max_t_len)

# --- ВАРИАНТ В: Чередование символов без двух одинаковых подряд ---
cur = max_alt = 1
for i in range(1, len(s)):
    if s[i] != s[i - 1]:
        cur += 1
        if cur > max_alt: max_alt = cur
    else:
        cur = 1
print("Максимальная длина без одинаковых подряд:", max_alt)

Анти-примеры (Типичные ошибки vs Как делать правильно)

Как делать НЕ надо:

Ошибка: Вложенные циклы 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 Открыть в тренажере СмартКИМ