ЕГЭОГЭЕНТ
РУҚА
Задания № 10, 27 · ЕГЭ

Повторяющиеся фрагменты

Как находить одинаковые подстроки и повторяющиеся части строки
2 мин чтенияСложность: Обновлено 29 сентября 2026

Повторяющиеся фрагменты — это одинаковые части строки, которые встречаются в ней два или более раз. Их ищут, сравнивая участки строки одинаковой длины и проверяя, совпадают ли символы на соответствующих позициях.

Повторяющийся фрагментСлово «фрагмент» означает часть целого, а «повторяющийся» — встречающийся снова.
Повторяющийся фрагмент строки — это подстрока, которая встречается в исходной строке не менее двух раз. Совпадения должны иметь одинаковую последовательность символов; обычно отдельно указывают, могут ли найденные вхождения пересекаться.

Как проверяют повторение

Сначала выбирают длину фрагмента \(k\). Затем рассматривают все возможные участки строки длины \(k\) и сравнивают их попарно. Для позиций \(i\) и \(j\) фрагменты совпадают, если символы от \(i\) до \(i+k-1\) равны символам от \(j\) до \(j+k-1\). Перебирать можно только такие позиции, чтобы фрагмент полностью помещался в строке.

\[s[i\dots i+k-1]=s[j\dots j+k-1],\qquad 0\le i<j\le n-k\]

На практике часто используют поиск подстроки: сначала выделяют возможный фрагмент, затем находят его следующее вхождение, начиная поиск после предыдущей позиции. Если требуется найти все варианты, перебирают разные длины и начальные позиции.

№
Пример

В строке ABABABA фрагмент ABA встречается с позиций 1 и 3, если считать позиции с единицы. Эти вхождения пересекаются: первое заканчивается на третьей позиции, а второе начинается на третьей. Поэтому важно заранее уточнить, разрешены ли пересечения.

!
Не путайте с периодом строки

Повторяющийся фрагмент может встретиться несколько раз, но это ещё не означает, что вся строка построена из одинаковых блоков. Например, в ABACABA фрагмент ABA повторяется, однако вся строка не является повторением одного блока. Для полной регулярности используют понятие периода строки.

Проверка

Какой фрагмент повторяется в строке ABCAB?

Главное за минуту

Главное

  • Повторяющийся фрагмент — подстрока, встречающаяся в строке не менее двух раз.
  • Для проверки сравнивают участки одинаковой длины и соответствующие символы.
  • Повторение отдельных фрагментов не всегда означает наличие периода всей строки.