Задание 24: Программирование. Обработка символьной информации

1. Общая информация о задании

• Уровень сложности: высокий (Часть 2)
• Максимальный балл: 1
• Примерное время выполнения: около 18 минут
• Формат файла: .txt — одна длинная строка символов (до 10⁶ символов)
• Формат ответа: одно число (или несколько — читать условие)

Суть: прочитать строку из файла и найти подстроку максимальной (или минимальной) длины, удовлетворяющую условию. Ручной разбор невозможен — нужна программа на Python.

Задания: N24. Задания Я.Учебник | N24. Банк заданий

Материалы курса:

• Часть 1 — типы задач, replace, однопроходный алгоритм
• Часть 2 — арифметические выражения, regex
• Часть 3 — запрещённые соседства, replace + split
• Часть 4 — точное число вхождений, склейка фрагментов

2. Считывание файла

В задании 24 файл — одна строка без переводов строк (или одна очень длинная строка).

s = open('24.txt').readline()

или с автозакрытием:

with open('24.txt') as f:
    s = f.readline()

Не используй readlines() без необходимости — файл обычно состоит из одной строки.

3. Три основных метода решения

На экзамене выбирай метод, который уверенно пишешь. Ответ лучше проверить вторым способом.

4. Четыре типа заданий

5. Метод 1: однопроходный алгоритм

Когда: нужна максимальная длина цепочки, где условие проверяется на каждом шаге (соседние символы различны, все символы одинаковые, запрещена пара KL…).

Шаблон

s = open('24.txt').readline()
mx = cur = 1   # или cur = 0 — смотреть условие

for i in range(1, len(s)):
    if условие_продолжения(s[i], s[i-1]):
        cur += 1
        mx = max(mx, cur)
    else:
        cur = 1   # или другое начальное значение

print(mx)

Пример: максимальная цепочка одинаковых символов A

s = open('24.txt').readline()
mx = cur = 1
for i in range(1, len(s)):
    if s[i] == s[i-1] == 'A':
        cur += 1
        mx = max(mx, cur)
    else:
        cur = 1
print(mx)

Пример: соседние символы различны

s = open('24.txt').readline()
mx = cur = 1
for i in range(1, len(s)):
    if s[i] != s[i-1]:
        cur += 1
        mx = max(mx, cur)
    else:
        cur = 1
print(mx)

Пример: запрещена пара KL или LK

s = open('24.txt').readline()
mx = cur = 1
for i in range(1, len(s)):
    if (s[i] == 'K' and s[i-1] == 'L') or (s[i] == 'L' and s[i-1] == 'K'):
        cur = 1
    else:
        cur += 1
        mx = max(mx, cur)
print(mx)

6. Метод 2: replace + split

Когда: два (или более) символа не должны стоять рядом — вставляем разделитель между запрещёнными парами и ищем самый длинный фрагмент.

Идея

1. replace('AB', 'A B') — вставить разрыв между A и B
2. split() — разбить строку на фрагменты
3. max(len(x) for x in parts) — длина самого длинного

Пример: A, B, C — нет подряд идущих A и B

s = open('24.txt').readline()
s = s.replace('AB', 'A B').replace('BA', 'B A')
parts = s.split()
print(max(len(x) for x in parts))

Пример: только символ C (остальные — разделители)

s = open('24.txt').readline()
s = s.replace('A', ' ').replace('B', ' ')
parts = s.split()
print(max(len(x) for x in parts))

Пример: KL и LK запрещены

s = open('24.txt').readline()
s = s.replace('KL', 'K L').replace('LK', 'L K')
print(max(len(x) for x in s.split()))

Важно: между символами нужен разрыв — 'A B', а не 'AB' → 'A'. Иначе длина фрагмента будет неверной.

7. Метод 3: регулярные выражения

Когда: сложный шаблон — чередование букв, символы из алфавита СС, арифметические выражения.

import re

s = open('24.txt').readline()

# найти все подходящие подстроки
matches = re.findall(r'шаблон', s)
print(max(len(m) for m in matches))

# или с позициями
matches = re.finditer(r'шаблон', s)
print(max(len(m.group()) for m in matches))

Тип 1: гласная + согласная, повторяется

import re

s = open('24.txt').readline()
pattern = r'(?:[AE][BCD])+'
matches = re.finditer(pattern, s)
print(max(len(m.group()) for m in matches))

Тип 2: корректное арифметическое выражение

Число без ведущих нулей: 0 или [1-9][0-9]*. Выражение: Число (операция Число)*.

import re

s = open('24.txt').readline()
num = r'(?:0|[1-9][0-9]*)'
pattern = rf'{num}(?:[+*-]{num})*'

matches = re.finditer(pattern, s)
print(max(len(m.group()) for m in matches))

Выражение со значением 0

Каждое слагаемое должно содержать умножение на 0:

import re

s = open('24.txt').readline()
num = r'(?:0|[1-9][0-9]*)'
mult = rf'(?:{num}\*)*0(?:\*{num})*'
pattern = rf'{mult}(?:\+{mult})*'

matches = re.finditer(pattern, s)
print(max(len(m.group()) for m in matches))

Чётные числа в выражении

num = r'(?:[1-9][0-9]*[02468]|[02468])'
pattern = rf'{num}(?:[+*]{num})+'

8. Метод 4: replace + split + склейка (тип 4)

Когда: в подстроке подстрока/буква должна встречаться ровно N раз.

Идея (часть 4)

1. Разбить строку по искомой комбинации: replace("AB", "A B").split()
2. Чтобы AB встретилась ровно 21 раз — склеить 22 соседних фрагмента через "AB"
3. Перебрать все окна из 22 фрагментов, взять максимальную длину

s = open('24.txt').readline()
parts = s.replace('AB', 'A B').split()

mx = 0
k = 21          # AB должна встретиться ровно 21 раз → 22 фрагмента
for i in range(len(parts) - k):
  # склеиваем parts[i] .. parts[i+k] через 'AB'
    candidate = 'AB'.join(parts[i:i + k + 1])
    mx = max(mx, len(candidate))

print(mx)

Ровно 2 буквы A в подстроке

s = open('24.txt').readline()
parts = s.replace('A', ' A ').split()

mx = 0
for i in range(len(parts) - 2):
    candidate = 'A'.join(parts[i:i + 3])   # 3 фрагмента → 2 буквы A между ними
    mx = max(mx, len(candidate))

print(mx)

9. Скользящее окно (два указателя)

Когда: запрещена подстрока фиксированной длины (например, XZZY), или нужно ограничить количество символов в окне.

s = open('24.txt').readline()
bad = 'XZZY'
L = mx = 0

for R in range(len(s)):
    while s[L:R+1].find(bad) != -1:
        L += 1
    mx = max(mx, R - L + 1)

print(mx)

10. Полезные операции со строками

Модуль re — краткая шпаргалка

11. Алгоритм решения на экзамене

1. Прочитать условие: что в файле, что искать (длина / значение / количество)
2. Определить тип (1–4) и выбрать метод
3. Считать строку: s = open('24.txt').readline()
4. Написать проверку условия или шаблон
5. Найти ответ: max длины / min значения / count
6. Вывести print(ответ)
7. Проверить на короткой тестовой строке вручную

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

13. Краткий чек-лист

1. s = open('24.txt').readline()
2. Какой тип задачи? (шаблон / арифметика / не рядом / ровно N раз)
3. Выбрать метод: однопроходный / replace+split / re / окно
4. Написать код, вывести ответ
5. Убрать отладочные print перед сдачей

14. Источники

• Учебник ЕГЭ по информатике — future-step.ru
• Обработка текста — Школа Виктора Комлева
• Методы обработки строк — Поляков
• Задание 24 — egeturbo.ru