9 мин чтениястрокифайлподстрокаскользящее окнозадание 24КЕГЭ
Строки и анализ файлов: шаблоны для задания 24
Чтение строки из файла, подсчёт вхождений, серии одинаковых символов, скользящее окно, регулярные выражения и типичные ловушки.
Открываем тему…
Чтение и подготовка данных
В задании 24 дан текстовый файл с одной строкой длиной до 10⁶ символов (буквы, иногда цифры). Прочитайте строку, уберите символ перевода строки и работайте с ней как с обычной строкой Python. Решение должно быть линейным: один проход, без вложенных циклов и без многократных replace по всей строке.
- s = open('24.txt').readline().strip() — чтение единственной строки.
- Серия одинаковых символов: счётчик, который растёт при совпадении с предыдущим символом и обнуляется при несовпадении.
- Подсчёт вхождений с перекрытием: цикл по позициям или регулярное выражение с опережающей проверкой re.findall('(?=ABA)', s).
- Разбиение по запрещённому символу: max(map(len, s.split('Z'))) — длина самого длинного фрагмента без Z.
- Подстрока с ограничением на число различных букв — метод двух указателей (скользящее окно) с частотным словарём.
- Частоты символов: from collections import Counter; Counter(s).most_common(3).
ПримерСамая длинная цепочка без одинаковых соседей
Дана строка AABCABCCABABC. Какова наибольшая длина подстроки, в которой нет двух одинаковых соседних символов?
Решение
Идём по строке и поддерживаем длину текущей цепочки: если символ отличается от предыдущего, увеличиваем её, иначе сбрасываем в 1.
s = 'AABCABCCABABC'
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) # 6
Наибольшая цепочка — ABCABC (позиции 2–7) длиной 6; такая же длина у CABABC.
ПримерПодстрока не более чем с двумя различными буквами
Найдите длину самой длинной подстроки строки ABACCCBAABB, содержащей не более двух различных букв.
Решение
Двигаем правую границу окна и сдвигаем левую, пока в окне больше двух различных букв.
s = 'ABACCCBAABB'
best = left = 0
cnt = {}
for right, ch in enumerate(s):
cnt[ch] = cnt.get(ch, 0) + 1
while len(cnt) > 2:
cnt[s[left]] -= 1
if cnt[s[left]] == 0:
del cnt[s[left]]
left += 1
best = max(best, right - left + 1)
print(best) # 5
Лучшее окно — BAABB (буквы A и B).
ПримерВхождения с перекрытием
Сколько раз подстрока ABA встречается в строке ABABABA?
Решение
Метод count() не учитывает перекрывающиеся вхождения: 'ABABABA'.count('ABA') даёт 2. Правильный подсчёт — перебор всех начал окна длины 3:
s = 'ABABABA'
print(sum(1 for i in range(len(s) - 2) if s[i:i + 3] == 'ABA')) # 3
Вхождения начинаются в позициях 0, 2 и 4.
ПримерДлина фрагмента без запрещённого символа
Строка ABZCDEZAB разделена символами Z. Найдите длину самого длинного фрагмента без Z.
Решение
'ABZCDEZAB'.split('Z') даёт ['AB', 'CDE', 'AB'], максимальная длина — 3. В коде: max(len(part) for part in s.split('Z')). Приём работает и для файла на миллион символов.
ПримерСамая длинная серия одинаковых символов
Дана строка «AABBBBCCAAAABBC». Найдите длину самой длинной цепочки из одинаковых подряд идущих символов.
Решение
Просматриваем строку слева направо, поддерживая длину текущей серии: если символ совпал с предыдущим, увеличиваем счётчик, иначе сбрасываем в 1; максимум запоминаем.
s = 'AABBBBCCAAAABBC'
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)
Серии: AA (2), BBBB (4), CC (2), AAAA (4), BB (2), C (1). Наибольшая длина — 4. Тот же приём работает для строки длиной в миллионы символов: один проход, O(n).
ПримерСколько раз встречается шаблон XYX
В строке «ABACABABCBCB» посчитайте количество позиций i, для которых символ на позиции i совпадает с символом на позиции i + 2 (то есть цепочка из трёх символов имеет вид XYX; Y может быть равно X).
Решение
Перебираем начала всех троек и сравниваем s[i] с s[i + 2]:
s = 'ABACABABCBCB'
print(sum(1 for i in range(len(s) - 2) if s[i] == s[i + 2]))
Подходящие позиции (нумерация с 1): 1, 3, 5, 6, 8, 9, 10 — всего 7. Цепочки могут пересекаться: считаются все начальные позиции шаблона, а не непересекающиеся вхождения.