Поиск и замена символов в текстовом редакторе — ЕГЭ, задание 10

Коротко о главном

Задание 10 проверяет умение считать количество вхождений подстроки в текст (в том числе перекрывающихся) и понимать, как меняется длина текста при операции «найти и заменить». Ключевые навыки: отличать поиск неперекрывающихся вхождений от всех вхождений, аккуратно считать длину до и после замены, работать с граничными случаями (начало/конец строки, повторяющиеся буквы).

Определения и формулы/правила

Понятие	Пояснение
Вхождение подстроки	Позиция в тексте, начиная с которой подряд идущие символы совпадают с искомой подстрокой
Неперекрывающиеся вхождения	Считаются при обычном последовательном поиске: после найденного вхождения поиск продолжается после его конца
Перекрывающиеся вхождения	Считаются все позиции, где подстрока встречается, даже если вхождения «накладываются» друг на друга (поиск продолжается со следующего символа)
Замена (Find & Replace)	Каждое найденное вхождение подстроки $S_1$ заменяется на подстроку $S_2$. Обычно замена идёт по неперекрывающимся вхождениям слева направо
Длина текста после замены	$$L_{new} = L_{old} + N\cdot(len(S_2) - len(S_1))$$ где $N$ — число замен, $len(S_1)$, $len(S_2)$ — длины искомой и заменяющей подстрок

Важное правило неперекрывающегося поиска: если подстрока найдена на позиции $i$ длиной $k$, следующий поиск начинается с позиции $i+k$, а не с $i+1$.

Правило перекрывающегося поиска: после нахождения вхождения на позиции $i$ следующий поиск начинается с позиции $i+1$.

Как применять

Пример 1. Подсчёт неперекрывающихся вхождений. Текст: ААААА, искомая подстрока: АА. Ищем слева направо: позиция 1 (символы 1–2) — вхождение, следующий поиск с позиции 3: символы 3–4 — вхождение, следующий поиск с позиции 5 — символов не хватает. Итого неперекрывающихся вхождений: 2.

Пример 2. Подсчёт перекрывающихся вхождений. Тот же текст ААААА, та же подстрока АА. Проверяем позиции 1,2,3,4: на каждой из них найдётся АА (1-2, 2-3, 3-4, 4-5). Итого перекрывающихся вхождений: 4.

Пример 3. Длина текста после замены. В тексте длиной 200 символов подстроку кот (3 символа) заменили на собака (6 символов), замена произошла 5 раз. $$L_{new} = 200 + 5\cdot(6-3) = 200+15 = 215$$

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

• Путают перекрывающиеся и неперекрывающиеся вхождения — читайте формулировку задачи внимательно: «сколько раз встречается» обычно означает перекрывающийся поиск, «сколько раз можно заменить» — неперекрывающийся.
• Не учитывают вхождения на границах текста (в начале или конце строки).
• Забывают, что после замены длина текста меняется, и при повторном поиске в новом тексте позиции вхождений уже другие.
• Ошибаются в знаке при вычислении $L_{new}$, если $len(S_2) < len(S_1)$ (длина текста уменьшается).
• Считают вхождения подстроки, которая сама состоит из повторяющихся символов, без учёта правила сдвига поиска (путают на сколько символов сдвигаться после находки).

Где встречается на экзамене

Тема — основа задания 10 ЕГЭ по информатике. Формулировки: «Сколько раз строка X встречается в тексте (в том числе с пересечениями/без пересечений)?», «Определите длину текста после замены всех вхождений подстроки A на подстроку B», «Сколько символов было заменено суммарно». Часто комбинируется с обработкой большого текстового файла программным способом (Python, Pascal), но в базовой формулировке достаточно ручного подсчёта по описанным правилам.