🔴 Сложный ⏱️ 50 минут

Алгоритмы на строках

📋 Содержание урока

Алгоритмы на строках 🧵

Представь, что ты готовишь корпус из миллиона пользовательских отзывов для обучения модели тональности. Прежде чем токенизатор увидит хоть одно предложение, тебе нужно почистить текст: найти и вырезать HTML-теги, обнаружить повторяющиеся спам-фразы, выделить упоминания брендов, схлопнуть множественные пробелы. Каждая из этих операций на своём базовом уровне — это один и тот же вопрос: встречается ли данная последовательность символов (подстрока-паттерн) внутри другой, гораздо более длинной последовательности (текста), и если да — где именно. Кажется, что это тривиальная задача, которую в Python решает один вызов text.find(pattern) или re.search(...), — и для отзыва длиной в пару сотен символов это действительно так. Но когда паттернов тысячи, а текста — гигабайты, то, что происходит внутри find, перестаёт быть деталью реализации и превращается в вопрос, определяющий, уложится твой пайплайн предобработки в приемлемое время или будет работать часами.

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

В этом уроке ты разберёшь все три пути по очереди. Начнёшь с наивного посимвольного поиска — самого простого и самого медленного варианта, увидишь, на каких именно данных он проваливается. Затем перейдёшь к алгоритму Кнута-Морриса-Пратта (КМП) — классике, которая с помощью одной вспомогательной структуры, префикс-функции, гарантирует линейную сложность независимо от входа. Дальше — полиномиальное хеширование строк и алгоритм Рабина-Карпа, где поиск подстроки превращается в сравнение чисел, а не символов, — и именно эта идея напрямую связывает сегодняшний урок с хеш-таблицами и техникой хеширования признаков (feature hashing) из урока про хеш-таблицы. Завершишь коротким разбором поиска палиндромов — отдельной, но родственной задачи о симметрии внутри строки.

Мотивация здесь не абстрактная: строка как последовательность символов, с которой работают алгоритмы этого урока, — это ровно то, с чем сталкивается почти любой NLP-пайплайн задолго до того, как в дело вступает нейросеть. Поиск и замена паттернов перед токенизацией, дедупликация похожих документов, детектирование плагиата, построение индексов для полнотекстового поиска, сжатие данных — за каждой из этих задач стоит один из алгоритмов, который ты увидишь ниже.

История

Задача поиска подстроки в тексте была прекрасно известна и решаема наивным способом задолго до появления компьютеров — текстовые редакторы реализовывали такой поиск ещё в 1960-х. Переломный момент случился в начале 1970-х, когда теоретик Стивен Кук, изучая нижние границы сложности распознавания языков на машинах Тьюринга с одной лентой, фактически поставил вопрос: а можно ли искать образец в тексте за время, линейно зависящее от длины входа, а не квадратично? Дональд Кнут, познакомившись с этой постановкой, вместе с Вон Праттом в середине 1970-х построил алгоритм с доказуемой линейной сложностью. Почти одновременно и независимо к тому же результату пришёл Джеймс Моррис — он занимался вполне практической задачей, реализацией текстового редактора, и хотел избавиться от квадратичного замедления поиска на «неудобных» текстах. Три автора объединили результаты в одну статью «Fast Pattern Matching in Strings», опубликованную в SIAM Journal on Computing в 1977 году, — с тех пор алгоритм и носит имя всех троих: Кнута-Морриса-Пратта.

Алгоритм Рабина-Карпа появился десятилетием позже, в 1987 году, в статье Майкла Рабина и Ричарда Карпа. Их идея шла из другой области — из теории вероятностных алгоритмов, которую оба автора активно развивали (Рабин известен также вероятностным тестом простоты числа, названным его именем). Вместо того чтобы анализировать структуру паттерна, как это делает КМП, Рабин и Карп предложили свести сравнение строк к сравнению чисел — хешей, — что радикально ускоряет поиск сразу нескольких паттернов одновременно и легло в основу практических систем обнаружения плагиата и поиска повторяющихся фрагментов в больших массивах документов.

Палиндромы — куда более древняя тема, само слово происходит от греческого «palíndromos», «бегущий назад». Интерес к вычислительному поиску палиндромов оформился позже: в 1975 году Гленн Манакер предложил алгоритм, который находит все палиндромные подстроки строки за линейное время — асимптотическое улучшение по сравнению с очевидным квадратичным перебором центров, о котором ты узнаешь в этом уроке.

Наивный поиск подстроки

Интуиция

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

Именно в этом «начинаем заново» и кроется главная слабость наивного алгоритма: он не запоминает ничего о частичных совпадениях, из-за чего на определённых входах вынужден повторно сравнивать одни и те же символы снова и снова.

Алгоритм

Наивный поиск подстроки:

Пусть text — текст длины $n$, pattern — образец длины $m$.

Для каждой стартовой позиции $i$ от $0$ до $n-m$ включительно: сравнить text[i:i+m] с pattern посимвольно, начиная с индекса $j=0$.

Если на каком-то шаге text[i+j] != pattern[j] — сравнение на этой позиции провалилось, перейти к позиции $i+1$.

Если дошли до $j=m$ без единого несовпадения — зафиксировать вхождение на позиции $i$.

Вернуть список всех найденных позиций.

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    positions = []

    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            positions.append(i)

    return positions

Сложность в худшем случае — $O(n \cdot m)$: для каждой из $n-m+1 \approx n$ стартовых позиций может потребоваться до $m$ сравнений.

Разбор примеров

Пример 1 (типичная NLP-задача). Найти все вхождения слова "hello" в тексте "hello world, hello python, hello again".

Пробегаем по всем стартовым позициям. При $i=0$: text[0:5]="hello", все 5 символов совпадают с pattern — фиксируем позицию 0. Дальше при $i=1..12$ сравнения проваливаются на первом же символе (кроме случайных совпадений отдельных букв, которые тут же обрываются на 2–3 символе). При $i=13$: text[13:18]="hello" — снова полное совпадение. При $i=27$: text[27:32]="hello" — третье совпадение.

Ответ: позиции [0, 13, 27] — ровно три вхождения слова, что типично при поиске и замене паттернов перед токенизацией (например, чтобы вырезать все упоминания стоп-слова или служебной фразы).

Пример 2 (худший случай). Найти вхождения pattern="aaab" в text="aaaaaaaaab" (девять символов a, затем один b).

При $i=0$: сравниваем "aaaa" с "aaab" — первые три символа совпадают (a,a,a), четвёртый — text[3]='a' против pattern[3]='b' — провал на 4-м сравнении. Ровно то же самое повторяется при $i=1,2,3,4,5$: три успешных сравнения и провал на четвёртом, потому что вплоть до позиции 8 в тексте стоят одни a. Только при $i=6$ окно text[6:10]="aaab" совпадает с паттерном полностью — успех за 4 сравнения.

Итого: 6 неудачных попыток по 4 сравнения плюс одна удачная попытка в 4 сравнения — 28 элементарных сравнений на тексте длиной всего 10 символов. Замени a на любую другую повторяющуюся часть и увеличь длину текста до миллиона символов — и число сравнений будет расти как $n \cdot m$, а не как $n$.

Пример 3 (лучший случай). Найти pattern="xyz" в text="abcdefgh".

Ни один символ текста не совпадает с 'x' — первым символом паттерна, поэтому на каждой из 6 стартовых позиций сравнение обрывается после одной-единственной проверки. Итого 6 сравнений на тексте длиной 8 — почти $O(n)$, потому что символы паттерна и текста почти никогда не совпадают даже частично.

Разница между примером 2 и примером 3 наглядно показывает: асимптотика $O(nm)$ — это именно худший случай, который реализуется на текстах с повторяющейся структурой (что для естественного языка совсем не редкость — подумай о длинных последовательностях пробелов, повторяющихся символах в спам-тексте или о строках ДНК из четырёх букв).

Почему это важно

Наивный поиск — не «плохой» алгоритм, который нужно немедленно забыть: для разового поиска короткого слова в тексте из пары тысяч символов разница между $O(n)$ и $O(nm)$ незаметна на глаз, а код при этом максимально прост и очевиден. Проблема начинается там, где паттернов много, текст велик или содержит периодичные фрагменты (что типично и для естественного языка, и, ещё сильнее, для биологических последовательностей). Именно эта уязвимость наивного подхода к «неудобным» входам — прямая мотивация для алгоритма Кнута-Морриса-Пратта, который убирает зависимость сложности от структуры данных вообще.

Префикс-функция и алгоритм Кнута-Морриса-Пратта

Интуиция

Возьми паттерн "ABABCABAB" и представь, что при сравнении с текстом ты успешно сопоставил первые четыре символа — "ABAB" — а на пятом произошло несовпадение. Наивный алгоритм в этой ситуации просто сдвигает окно на одну позицию и начинает сравнение с нуля — полностью игнорируя тот факт, что он только что уже знает, какие символы текста стоят на нескольких следующих позициях: это те самые "ABAB", которые только что совпали с паттерном. Раз ты знаешь, что последние сопоставленные символы текста — "ABAB", а паттерн начинается с "AB" — не логичнее ли сразу проверить, не совпадает ли начало паттерна с этим уже известным хвостом текста, вместо того чтобы сравнивать заново?

Именно эту идею формализует префикс-функция паттерна: она заранее, ещё до начала поиска по тексту, отвечает на вопрос «если я знаю, что совпали первые $i$ символов паттерна, а дальше провал — на сколько символов паттерна я могу сразу продвинуться, не теряя ни одного потенциального совпадения?». Вся эта информация зависит только от самого паттерна и вычисляется один раз, а затем многократно используется при проходе по тексту.

Алгоритм

Префикс-функция. Для строки pattern длины $m$ префикс-функция $\pi[i]$ — это длина наибольшего собственного префикса подстроки pattern[0..i] (то есть префикса, который короче самой этой подстроки), который одновременно является и её суффиксом. По определению $\pi[0] = 0$.

Построение префикс-функции:

Завести массив pi длины $m$, pi[0] = 0, переменную k = 0 (длина текущего совпадения).

Для каждого $i$ от $1$ до $m-1$: пока k > 0 и pattern[i] != pattern[k] — откатить k = pi[k-1].

Если pattern[i] == pattern[k] — увеличить k на 1.

Записать pi[i] = k и перейти к следующему $i$.

Поиск по тексту (сам алгоритм КМП):

Построить pi для pattern. Завести q = 0 — число уже совпавших с текущим положением в тексте символов паттерна.

Для каждого символа text[i] слева направо: пока q > 0 и text[i] != pattern[q] — откатить q = pi[q-1].

Если text[i] == pattern[q] — увеличить q на 1.

Если q == m — зафиксировать вхождение на позиции i - m + 1, затем откатить q = pi[q-1] (чтобы продолжить поиск, в том числе перекрывающихся вхождений).

def prefix_function(pattern):
    m = len(pattern)
    pi = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = pi[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        pi[i] = k
    return pi


def kmp_search(text, pattern):
    pi = prefix_function(pattern)
    n, m = len(text), len(pattern)
    positions = []
    q = 0

    for i in range(n):
        while q > 0 and text[i] != pattern[q]:
            q = pi[q - 1]
        if text[i] == pattern[q]:
            q += 1
        if q == m:
            positions.append(i - m + 1)
            q = pi[q - 1]

    return positions

Ключевое доказательство эффективности — амортизационное: индекс i по тексту за весь проход увеличивается ровно $n$ раз (по одному разу за итерацию цикла for), а переменная q может увеличиваться максимум $n$ раз суммарно (не больше одного раза на каждую итерацию for) — значит, и уменьшаться (в цикле while через откат pi[k-1]) она тоже может суммарно не больше $n$ раз. Отсюда общее число элементарных операций — $O(n + m)$ (плюс $O(m)$ на построение самой префикс-функции тем же приёмом).

Разбор примеров

Пример 1 (построение префикс-функции). Построить pi для pattern = "ababaca".

$\pi[0]=0$ по определению. $i=1$ ('b'): $k=0$, pattern[1]='b' не равно pattern[0]='a' — не совпало, $\pi[1]=0$. $i=2$ ('a'): $k=0$, pattern[2]='a' равно pattern[0]='a' — совпало, $k=1$, $\pi[2]=1$. $i=3$ ('b'): $k=1$, pattern[3]='b' равно pattern[1]='b' — совпало, $k=2$, $\pi[3]=2$. $i=4$ ('a'): $k=2$, pattern[4]='a' равно pattern[2]='a' — совпало, $k=3$, $\pi[4]=3$. $i=5$ ('c'): $k=3$, pattern[5]='c' не равно pattern[3]='b' — откат $k=\pi[2]=1$; pattern[5]='c' не равно pattern[1]='b' — откат $k=\pi[0]=0$; pattern[5]='c' не равно pattern[0]='a' — совпадения нет, $\pi[5]=0$. $i=6$ ('a'): $k=0$, pattern[6]='a' равно pattern[0]='a' — совпало, $k=1$, $\pi[6]=1$.

Ответ: $\pi = [0, 0, 1, 2, 3, 0, 1]$.

Пример 2 (поиск с откатом при несовпадении). Найти вхождение pattern="ABABCABAB" в text="ABABDABABCABAB".

Сначала строим префикс-функцию паттерна (тем же приёмом, что в примере 1): $\pi = [0,0,1,2,0,1,2,3,4]$.

Дальше проходим по тексту с q=0. На $i=0..3$ символы текста "ABAB" последовательно совпадают с pattern[0..3]="ABAB", q растёт до 4. На $i=4$ символ текста — 'D', а pattern[4]='C' — несовпадение. Откатываем: q = pi[3] = 2, сравниваем text[4]='D' с pattern[2]='A' — снова несовпадение; откатываем q = pi[1] = 0, сравниваем text[4]='D' с pattern[0]='A' — тоже несовпадение, но q уже 0, откатывать больше некуда, переходим к следующему символу текста с q=0.

С $i=5$ по $i=13$ текст даёт последовательность "ABABCABAB", которая посимвольно совпадает с паттерном — q растёт с 0 до 9 без единого отката. На $i=13$ достигнуто q=9=m — зафиксировано вхождение на позиции $13-9+1=5$.

Ответ: вхождение найдено на позиции 5; при этом ни один символ текста не был просмотрен дважды в ходе основного цикла — откат q через pi произошёл всего дважды на позиции $i=4$, что и есть амортизированная плата за пропущенное совпадение.

Пример 3 (перекрывающиеся вхождения). Найти все вхождения pattern="aaaa" в text="aaaaaaaaaa" (десять символов a).

Префикс-функция паттерна "aaaa": $\pi=[0,1,2,3]$ (каждый следующий символ повторяет предыдущий, поэтому k растёт без откатов). При поиске q растёт вместе с i: на $i=3$ достигается q=4=m — вхождение на позиции $3-4+1=0$. После фиксации откатываем q=\pi[3]=3 — не обнуляем полностью, а сохраняем информацию о том, что последние три символа уже совпадают. На $i=4$: text[4]='a'=pattern[3] — совпало, q=4 снова — вхождение на позиции $4-4+1=1$. Этот процесс повторяется до $i=9$, давая вхождения на позициях $0,1,2,3,4,5,6$ — семь перекрывающихся совпадений.

Ответ: позиции [0, 1, 2, 3, 4, 5, 6] — все семь возможных (перекрывающихся!) вхождений найдены за один линейный проход, потому что после каждого совпадения q откатывается не в ноль, а к pi[q-1], сохраняя уже известную информацию, а не выбрасывая её.

Почему это важно

Гарантия $O(n+m)$ независимо от содержимого текста — это ровно то, чего не хватало наивному алгоритму, и именно поэтому КМП (и его идейные родственники) лежат в основе промышленных инструментов текстового поиска: grep и родственные утилиты используют алгоритмы этого семейства, чтобы гарантированно быстро искать паттерн даже в текстах с длинными повторами. Для предобработки данных в NLP это значит одно: пайплайн очистки текста, использующий КМП-подобный поиск, не сорвёт время выполнения независимо от того, насколько «неудобным» (повторяющимся, периодичным) окажется конкретный документ в датасете — а гарантии такого рода критичны, когда обработка идёт по расписанию на терабайтах логов или пользовательского контента.

Хеширование строк и алгоритм Рабина-Карпа

Интуиция

И наивный поиск, и КМП в конечном счёте сравнивают символы: рано или поздно алгоритм смотрит на конкретную букву текста и конкретную букву паттерна и решает, совпадают они или нет. Хеширование предлагает принципиально другой путь: превратить каждую подстроку фиксированной длины в одно число — хеш — и сравнивать не строки целиком, а эти числа. Два разных числа гарантированно означают, что строки разные. Два одинаковых числа с высокой вероятностью означают, что строки совпадают, — но эту вероятность нужно подтвердить, потому что в принципе у двух разных строк может (редко, но может) получиться одинаковый хеш — это называется коллизией.

Ключевая техническая деталь, которая и делает хеширование пригодным именно для скользящего поиска подстроки: хеш окна текста можно пересчитывать не с нуля при каждом сдвиге, а за $O(1)$, зная лишь хеш предыдущего окна и то, какой символ ушёл, а какой пришёл. Это называется скользящим хешем (rolling hash).

Алгоритм

Полиномиальный хеш строки. Для строки $s$ длины $m$ с числовыми кодами символов $c_0, c_1, \dots, c_{m-1}$ (например, $c_i = \text{ord}(s_i)$) и простого основания $p$ (больше размера алфавита) хеш определяется как
$$H(s) = \left(c_0 \cdot p^{m-1} + c_1 \cdot p^{m-2} + \dots + c_{m-1} \cdot p^0\right) \bmod M$$
где $M$ — большое простое число-модуль, ограничивающее размер хеша и снижающее число коллизий.

Пересчёт хеша при сдвиге окна на один символ вправо (rolling hash). Если известен хеш окна s[i..i+m-1], то хеш следующего окна s[i+1..i+m] (убираем s[i], добавляем s[i+m]) вычисляется без полного пересчёта:
$$H(s[i{+}1..i{+}m]) = \Big(\big(H(s[i..i{+}m{-}1]) - c_i \cdot p^{m-1}\big) \cdot p + c_{i+m}\Big) \bmod M$$
Алгоритм Рабина-Карпа:

Вычислить хеш pattern и хеш первого окна text[0..m-1].

Для каждой стартовой позиции $i$: если хеш текущего окна текста равен хешу паттерна — обязательно сверить окно с паттерном посимвольно (защита от коллизии); при совпадении зафиксировать вхождение.

Пересчитать хеш следующего окна по формуле скользящего хеша за $O(1)$ и перейти к позиции $i+1$.

def rabin_karp_search(text, pattern, p=31, mod=1_000_000_007):
    n, m = len(text), len(pattern)
    if m > n:
        return []

    def code(ch):
        return ord(ch) - ord('a') + 1

    p_pow_m1 = pow(p, m - 1, mod)

    h_pattern = 0
    h_window = 0
    for i in range(m):
        h_pattern = (h_pattern * p + code(pattern[i])) % mod
        h_window = (h_window * p + code(text[i])) % mod

    positions = []
    for i in range(n - m + 1):
        if h_window == h_pattern and text[i:i + m] == pattern:
            positions.append(i)
        if i < n - m:
            h_window = ((h_window - code(text[i]) * p_pow_m1) * p + code(text[i + m])) % mod

    return positions

Средняя сложность — $O(n + m)$: пересчёт хеша окна и сравнение чисел — $O(1)$ на позицию, а посимвольная сверка выполняется лишь при совпадении хешей (что при хорошем модуле $M$ происходит редко и почти всегда означает настоящее совпадение). Худший случай — $O(n \cdot m)$, если модуль подобран неудачно и коллизии происходят на каждом шаге.

Разбор примеров

Пример 1 (вычисление хеша вручную). Вычислить $H(\text{"bca"})$ при $p=31$, $M=10^9+7$, коды $a{=}1, b{=}2, c{=}3$.

$$H = 2 \cdot 31^2 + 3 \cdot 31^1 + 1 \cdot 31^0 = 2 \cdot 961 + 93 + 1 = 1922 + 93 + 1 = 2016$$

Ответ: $H(\text{"bca"}) = 2016$.

Пример 2 (скользящий хеш). Дана строка "abcaa", окно длины $m=3$, $p=31$. Вычислить хеши окон "abc", "bca", "caa" — сначала напрямую, затем через формулу скользящего хеша, и убедиться, что результаты совпадают.

Напрямую. $H(\text{"abc"}) = 1\cdot31^2+2\cdot31+3 = 961+62+3=1026$. $H(\text{"caa"}) = 3\cdot31^2+1\cdot31+1=2883+31+1=2915$. ($H(\text{"bca"})=2016$ — уже посчитан в примере 1.)

Через скользящий хеш, от "abc" к "bca". Убираем 'a' (код 1), добавляем новый символ на позиции 3 — это 'a' (код 1): $H(\text{"bca"}) = (1026 - 1\cdot961)\cdot31 + 1 = 65\cdot31+1=2015+1=2016$ — совпадает с прямым вычислением.

От "bca" к "caa". Убираем 'b' (код 2), добавляем символ на позиции 4 — это 'a' (код 1): $H(\text{"caa"}) = (2016-2\cdot961)\cdot31+1 = 94\cdot31+1=2914+1=2915$ — снова совпадает.

Ответ: оба способа дают одинаковые хеши на каждом шаге — именно поэтому скользящий хеш можно безопасно использовать вместо полного пересчёта, экономя время на каждом сдвиге окна.

Пример 3 (полный поиск Рабина-Карпа). Найти pattern="bca" в text="abcaa".

Хеш паттерна $H(\text{"bca"})=2016$ (пример 1). Хеши окон текста, вычисленные в примере 2: "abc" → $1026$, "bca" → $2016$, "caa" → $2915$. Сравниваем последовательно: при $i=0$ хеш окна $1026 \ne 2016$ — пропускаем без единого посимвольного сравнения. При $i=1$ хеш окна $2016 = 2016$ — есть совпадение хешей, поэтому обязательно сверяем text[1:4]="bca" с pattern="bca" посимвольно — строки действительно равны, фиксируем вхождение. При $i=2$ хеш окна $2915 \ne 2016$ — пропускаем.

Ответ: вхождение найдено на позиции 1, при этом посимвольное сравнение потребовалось лишь один раз — ровно там, где хеши действительно совпали, а не на каждой из трёх позиций, как было бы при наивном поиске.

Почему это важно

Идея «сравнивать числа вместо строк» — это не изолированный трюк для одной конкретной задачи поиска подстроки, а общий принцип, который ты уже видел под другим углом в уроке про хеш-таблицы: там хеш-функция превращала произвольный ключ в индекс массива, здесь она превращает подстроку в число, которое можно сравнить за $O(1)$. Алгоритм Рабина-Карпа особенно выигрывает, когда нужно искать много паттернов одновременно (тогда хеши паттернов можно сложить в множество и сравнивать хеш каждого окна текста с этим множеством за $O(1)$) — это лежит в основе систем обнаружения плагиата и поиска дубликатов документов, где сравнивают не полные тексты, а наборы хешей их скользящих фрагментов (шинглов). А направление мысли «дорогая операция над строкой → дешёвая операция над числом» напрямую продолжается в хешировании признаков (feature hashing) из урока про хеш-таблицы: там текстовый признак (слово, n-грамма, идентификатор категории) точно так же хешируется в фиксированный числовой индекс вектора, без хранения словаря «значение → индекс», — та же самая идея, применённая не к поиску, а к векторизации текста перед подачей в модель.

Палиндромы и их поиск

Интуиция

Палиндром — строка, которая читается одинаково слева направо и справа налево: "шалаш", "довод", "казак". Задача поиска палиндрома внутри более длинной строки (например, самой длинной палиндромной подстроки) — родственница задачи поиска подстроки, но симметрия здесь ищется не относительно внешнего паттерна, а внутри самой строки, вокруг какого-то центра.

Самый очевидный подход — расширение от центра (expand around center): перебрать все возможные центры симметрии и для каждого расширяться наружу, пока символы слева и справа совпадают.

Алгоритм

Расширение от центра:

У строки длины $n$ всего $2n-1$ возможных центров симметрии: $n$ центров для палиндромов нечётной длины (центр — сам символ) и $n-1$ центров «между двумя символами» для палиндромов чётной длины.

Для каждого центра расширяться одновременно влево и вправо, пока символы на симметричных позициях совпадают и индексы не вышли за границы строки.

Как только расширение остановилось — зафиксировать длину найденного палиндрома и, если она больше текущего максимума, обновить лучший результат.

def expand(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return s[left + 1:right]


def longest_palindrome(s):
    best = ""
    for center in range(len(s)):
        odd = expand(s, center, center)
        even = expand(s, center, center + 1)
        for candidate in (odd, even):
            if len(candidate) > len(best):
                best = candidate
    return best

Сложность в худшем случае — $O(n^2)$: центров $2n-1 \approx n$, а расширение от каждого может занять до $O(n)$ шагов (например, на строке из одинаковых символов).

Разбор примеров

Пример 1 (проверка палиндрома). Проверить, является ли "шалаш" палиндромом.

Два указателя: left=0 ('ш'), right=4 ('ш') — совпадают. left=1 ('а'), right=3 ('а') — совпадают. left=2=right=2 ('л') — указатели встретились, проверка окончена.

Ответ: да, "шалаш" — палиндром.

Пример 2 (расширение от центра). Найти самую длинную палиндромную подстроку в "babad".

Пробуем центр $c=2$ (символ 'b', индексация с нуля: b-a-b-a-d). Расширение: left=2,right=2 — валидно (один символ). Шаг: left=1,right=3: s[1]='a', s[3]='a' — совпадают, продолжаем. Шаг: left=0,right=4: s[0]='b', s[4]='d' — не совпадают, останавливаемся. Результат расширения — s[1:4]="aba", длина 3.

Другие центры дают более короткие палиндромы (например, центр 0 — только "b", центр 1 — "bab" тоже длины 3). Максимум — 3 символа, среди кандидатов такой длины — "bab" (центр 1) и "aba" (центр 2).

Ответ: самая длинная палиндромная подстрока имеет длину 3 ("bab" или "aba").

Пример 3 (худший случай и алгоритм Манакера). Строка "aaaaaaaaaa" (десять a). Для каждого из 19 центров расширение доходит почти до границ строки — суммарная работа порядка $O(n^2)$, потому что все символы совпадают, и алгоритм не может остановиться рано ни на одном центре.

Именно на таких «максимально симметричных» строках квадратичная сложность расширения от центра становится заметной. Алгоритм Манакера решает эту проблему за линейное время: он переиспользует информацию о уже найденных палиндромах при переходе к следующему центру (идея, очень похожая на то, как префикс-функция КМП переиспользует уже известную информацию о совпадениях) — но полный вывод этого алгоритма выходит за рамки текущего урока: важно знать, что он существует и даёт $O(n)$ там, где наивное расширение от центра даёт $O(n^2)$.

Почему это важно

Поиск палиндромов — не только классическая олимпиадная задача, но и реальный инструмент: в биоинформатике палиндромные последовательности ДНК отмечают сайты, которые распознают рестрикционные ферменты, а сама пара «наивное $O(n^2)$-решение против линейного алгоритма Манакера» — ещё одна иллюстрация той же закономерности, которую ты уже видел на примере наивного поиска подстроки и КМП: как только становится понятно, какая именно избыточная работа повторяется, почти всегда находится способ её не повторять.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Наивным способом найти все позиции вхождения pattern="an" в text="banana".

Задание 2: Оценить максимальное число посимвольных сравнений наивного алгоритма для текста длины $n=100$ и паттерна длины $m=10$.

Задание 3: Текст длины $n=20$, паттерн длины $m=5$; первый символ паттерна ни разу не совпадает с текстом (образец в тексте отсутствует, и каждая попытка обрывается на первом же сравнении). Сколько сравнений сделает наивный алгоритм?

Задание 4: Написать функцию contains(text, pattern), которая наивным способом возвращает True/False, не собирая список всех позиций.

Задание 5: Дать определение префикс-функции своими словами и вычислить $\pi[2]$ для pattern="aab".

Задание 6: Записать формулу полиномиального хеша строки и объяснить смысл каждого символа в ней.

Задание 7: Вычислить $H(\text{"ab"})$ при $p=31$, коды $a{=}1$, $b{=}2$.

Задание 8: Проверить, является ли "потоп" палиндромом методом двух указателей.

Задание 9: Сколько центров симметрии нужно перебрать методом расширения от центра для строки длины 6?

Задание 10: Сформулировать одним предложением принципиальное отличие алгоритма КМП от наивного поиска.

Средние задания (11–20)

Задание 11: Построить префикс-функцию для pattern="aabaaab".

Задание 12: Алгоритмом КМП найти все (в том числе перекрывающиеся) вхождения pattern="aba" в text="ababababa".

Задание 13: Известно, что $\pi[3]=2$ для некоторого паттерна. Что это конкретно означает?

Задание 14: Вычислить $H(\text{"cab"})$ при $p=31$, коды $a{=}1,b{=}2,c{=}3$.

Задание 15: Дан текст "cabca", окно длины 3, $p=31$. Вычислить хеш окна "abc" через скользящую формулу, зная $H(\text{"cab"})=2916$.

Задание 16: Написать функцию одного шага скользящего хеша: по h_prev, коду ушедшего символа old_code, коду нового символа new_code, основанию p, модулю mod и предвычисленному p_pow_m1 вернуть хеш следующего окна.

Задание 17: Почему при совпадении хешей в алгоритме Рабина-Карпа всё равно необходимо сверять строки посимвольно?

Задание 18: Найти самую длинную палиндромную подстроку в "cbbd" методом расширения от центра.

Задание 19: Для pattern="aaaa" и text из десяти символов a алгоритм КМП после первого найденного совпадения откатывает q к $\pi[3]=3$, а не к 0. Объяснить, зачем, и перечислить все найденные позиции.

Задание 20: Для $n=10^6$, $m=1000$ сравнить порядок числа операций наивного алгоритма, КМП и Рабина-Карпа (средний случай).

Продвинутые задания (21–30)

Задание 21: Используя последнее значение префикс-функции, определить, является ли "abcabcabc" периодичной строкой, и найти длину минимального периода.

Задание 22: Тем же приёмом проверить, является ли "aabaaba" периодичной строкой.

Задание 23: Описать (без полного кода), как алгоритм Рабина-Карпа ищет за один проход по тексту сразу два паттерна одинаковой длины — pattern1="bc" и pattern2="ca" — в text="abcabc".

Задание 24: Объяснить, почему обычный позиционный полиномиальный хеш не подходит напрямую для проверки, является ли одна строка анаграммой (перестановкой символов) другой, и что нужно изменить.

Задание 25: С помощью хеширования (без прямого посимвольного сравнения всех пар) оценить число различных подстрок длины 3 в text="abcabc".

Задание 26: Если модуль $M$ выбран настолько неудачно, что хеш каждого окна текста искусственно совпадает с хешем паттерна, какой станет сложность алгоритма Рабина-Карпа и почему?

Задание 27: Реализовать проверку палиндрома через два указателя без использования срезов и встроенного reverse, и применить к "казак".

Задание 28: Перечислить все палиндромные подстроки строки "aaa" (считая каждую позицию отдельно) и объяснить, почему их количество максимально возможное для строки такой длины.

Задание 29: Есть список из десятков тысяч стоп-фраз (паттернов) и текст отзыва; нужно быстро проверить, содержится ли в тексте хотя бы одна из фраз, перед токенизацией. Какой из трёх разобранных подходов предпочтительнее и почему?

Задание 30: Для text="abababab" и pattern="abab" подсчитать точное число посимвольных сравнений наивного алгоритма и алгоритма КМП.

Частые ошибки

Ошибка 1. Используют наивный поиск подстроки на больших или периодичных текстах, не осознавая риска $O(n\cdot m)$.

Как выглядит: пайплайн предобработки текста годами работал быстро на тестовых данных, а на боевом датасете с длинными повторяющимися фрагментами (логи, спам, шаблонные фразы) внезапно замедлился в десятки раз.

Как правильно: для больших объёмов текста и заранее неизвестной структуры данных закладываться на алгоритм с гарантированной линейной сложностью — КМП или Рабина-Карпа — а не на наивный перебор.

Ошибка 2. Забывают откатывать k (или q) через префикс-функцию в цикле while при построении pi или при поиске КМП.

Как выглядит: код после несовпадения просто обнуляет счётчик (k = 0) вместо отката к pi[k-1] — алгоритм формально работает, но теряет всю линейность и по сути вырождается в наивный поиск, просто спрятанный за более сложным кодом.

Как правильно: каждое несовпадение при k > 0 должно приводить к отступлению k = pi[k-1], а не к обнулению — это и есть единственное место, где префикс-функция реально используется.

Ошибка 3. Путают, что сравнивается с чем при поиске по тексту: символ текста с pattern[q], а не наоборот, и не различают роли pi паттерна и текущего положения по тексту.

Как выглядит: пытаются построить отдельную префикс-функцию для текста или сравнивают text[i] с pattern[i] вместо pattern[q], теряя смысл переменной q как счётчика уже совпавших символов.

Как правильно: держать в голове, что pi строится один раз для паттерна и не меняется во время поиска, а q — это отдельная переменная состояния, отслеживающая, сколько символов паттерна уже совпало с текущим положением в тексте.

Ошибка 4. Забывают взять хеш по модулю на каждом промежуточном шаге при вычислении полиномиального хеша.

Как выглядит: модуль применяется только к финальному результату, а не к каждому промежуточному умножению и сложению — в Python это не приводит к переполнению (целые числа произвольной точности), но числа быстро становятся огромными и вычисления резко замедляются; в языках с фиксированной разрядностью (C++, Java) это вообще приводит к переполнению и некорректному результату.

Как правильно: брать % mod после каждой операции сложения и умножения, а не только в конце.

Ошибка 5. Сравнивают только хеши окна и паттерна в алгоритме Рабина-Карпа, не выполняя посимвольную проверку при совпадении.

Как выглядит: код фиксирует «найдено совпадение» сразу же, как только h_window == h_pattern, без строки if text[i:i+m] == pattern.

Как правильно: совпадение хешей — это лишь кандидат на совпадение, обязательная посимвольная сверка защищает от ложных срабатываний из-за коллизий.

Ошибка 6. При поиске палиндромов методом расширения от центра рассматривают только $n$ «одиночных» центров, забывая про $n-1$ «межсимвольных» центров для палиндромов чётной длины.

Как выглядит: функция перебирает центры только вида expand(s, i, i), пропуская expand(s, i, i+1) — в результате все палиндромы чётной длины (например, "bb") систематически не находятся.

Как правильно: на каждой итерации проверять оба варианта центра — и одиночный, и межсимвольный, — как показано в разобранном алгоритме.

Главное запомнить

Наивный поиск подстроки работает за $O(n\cdot m)$ в худшем случае — просто и достаточно для коротких, разовых поисков, но опасно для больших и периодичных текстов.
Худший случай наивного алгоритма реализуется на периодичных паттернах — длинных частичных совпадениях, которые проваливаются лишь на последнем символе окна.
Префикс-функция $\pi[i]$ паттерна — длина наибольшего собственного префикса подстроки pattern[0..i], который одновременно является её суффиксом; вычисляется один раз для паттерна и не зависит от текста.
Алгоритм Кнута-Морриса-Пратта использует префикс-функцию, чтобы при несовпадении не начинать сравнение заново, а откатиться к уже известному частичному совпадению — гарантированная сложность $O(n+m)$.
Полиномиальный хеш превращает строку в число через сумму кодов символов, взвешенных степенями простого основания $p$, по модулю большого простого $M$.
Скользящий хеш (rolling hash) пересчитывается за $O(1)$ при сдвиге окна на один символ — это и есть техническая основа алгоритма Рабина-Карпа.
Рабин-Карп сравнивает числа (хеши) вместо строк, но обязан подтверждать совпадение хешей посимвольной проверкой, чтобы не поймать ложное срабатывание из-за коллизии.
Поиск палиндрома методом расширения от центра — $O(n^2)$ в худшем случае из-за $2n-1$ центров, каждый из которых может потребовать до $O(n)$ шагов расширения; алгоритм Манакера снижает это до $O(n)$.
Общая идея всех трёх подходов к поиску подстроки — по-разному избегать повторной работы: либо через структуру самого паттерна (КМП), либо через превращение сравнения строк в сравнение чисел (хеширование).
Те же техники — хеширование строк, скользящее окно, анализ префиксов — прямая основа хеширования признаков (feature hashing) и предобработки текста в NLP-пайплайнах.

Связь с темами курса

Что нужно было знать до этого урока

Формально этот урок стоит на переборе с возвратом (backtracking, урок 273) — оттуда идёт общая философия «не повторять уже проверенные варианты работы», которая здесь выражается не явным откатом, а математическим анализом через префикс-функцию. Кроме того, необходимы базовые представления о массивах и списках и, что особенно важно для раздела о хешировании, понимание хеш-функций и модульной арифметики из урока о хеш-таблицах — именно оттуда взята сама идея превращения произвольных данных в число фиксированного диапазона и понятие коллизии.

Что изучить дальше

В следующем уроке, «275. Вычислительная геометрия», та же стратегия «раздели, реши по частям, объедини», которую ты уже видел в сортировке слиянием и быстрой сортировке, применяется к задачам про точки на плоскости — при этом идея скользящего окна и анализа локальной структуры данных, знакомая тебе по КМП и хешированию строк, снова всплывёт при поиске ближайшей пары точек. Дальше в курсе более сложные структуры для текста — суффиксные массивы и деревья, автомат Ахо-Корасик для многошаблонного поиска — прямо опираются на понятия из этого урока: префиксы, суффиксы, скользящие окна.

Где это нужно в жизни

🤖 ML/NLP. Поиск и замена паттернов перед токенизацией (удаление HTML-тегов, служебных символов, стоп-фраз), детектирование почти-дубликатов в обучающей выборке через шинглы и скользящие хеши, хеширование признаков (feature hashing) для превращения категориальных и текстовых признаков в фиксированный числовой вектор без хранения словаря.

🔍 Поисковые системы и текстовые редакторы. Реализация grep, find/replace, полнотекстовый поиск — все они опираются на алгоритмы гарантированной линейной сложности, а не на наивный перебор.

🧬 Биоинформатика. Поиск заданных мотивов и палиндромных последовательностей (сайтов рестрикции) в последовательностях ДНК — тот же алгоритмический аппарат, применённый к алфавиту из четырёх букв.

🕵️ Обнаружение плагиата и дедупликация. Сравнение документов через хеши скользящих фрагментов текста (шинглы) вместо посимвольного сравнения всего текста целиком.

Интересные факты

Джеймс Моррис независимо переоткрыл идею алгоритма КМП, работая над практической задачей — текстовым редактором Multics в начале 1970-х, — в то время как Кнут и Пратт пришли к тому же результату теоретическим путём, отвечая на вопрос Стивена Кука о нижних границах сложности. Редкий для информатики случай, когда теория и инженерная практика независимо сошлись к одному и тому же алгоритму.
Алгоритм Рабина-Карпа при поиске одного-единственного паттерна не всегда быстрее КМП на практике — константы у модульной арифметики выше, чем у простого сравнения символов, — но становится безальтернативным лидером при поиске сразу многих паттернов одинаковой длины, что и определило его нишу в системах обнаружения плагиата и дедупликации документов.
Алгоритм Манакера для поиска всех палиндромных подстрок за $O(n)$ был впервые описан в 1975 году, но стал по-настоящему массово известным лишь с распространением алгоритмических собеседований в 2000–2010-х — пример того, как красивый, но не самый разрекламированный результат десятилетиями ждёт своего часа в учебниках.
Стандартные методы поиска подстроки в CPython (str.find, оператор in) реализованы куда более сложным алгоритмом — «two-way» алгоритмом Крошмора-Перрена, — который сочетает элементы идей, похожих на КМП, с элементами алгоритма Бойера-Мура, и на практике часто быстрее «учебного» КМП именно за счёт умения пропускать сразу несколько символов текста при определённых несовпадениях.

Лайфхаки

Перед тем как писать свой алгоритм поиска подстроки для продакшена, всегда проверяй, не решает ли задачу штатный метод языка (str.find, in, модуль re) — переизобретать колесо руками имеет смысл прежде всего для обучения или для нестандартных условий вроде поиска сразу многих паттернов или потоковых данных.
Если несколько раз ловишь ошибку в реализации префикс-функции — распечатывай на каждом шаге тройку (i, k, pattern[i] vs pattern[k]) и сверяй с ручной трассировкой на маленьком примере вроде "ababaca": ошибка почти всегда становится видна за пару итераций.
Для хеширования строк в реальном коде (а не в учебных целях) используй два разных модуля и два разных основания одновременно (double hashing) — вероятность того, что коллизия произойдёт сразу по обоим хешам одновременно, исчезающе мала, и это часто дешевле постоянной посимвольной верификации.
При отладке скользящего хеша сверяй хотя бы одно окно «напрямую» (полным пересчётом с нуля) и «через скользящую формулу»: если результаты разошлись, ошибка почти всегда в степени $p^{m-1}$ — она либо посчитана для неправильной длины окна, либо не взята по модулю на каждом шаге.
Прежде чем применять расширение от центра для поиска палиндромов на длинных строках, прикинь, не является ли твой текст «плохим» случаем (много подряд идущих одинаковых символов) — если да, сразу закладывайся на квадратичное время или используй готовую реализацию алгоритма Манакера, а не пиши свою на скорую руку под дедлайн.
Если нужно быстро проверить периодичность строки, не пиши отдельный алгоритм — используй последнее значение префикс-функции: d = m - pi[m-1], и строка периодична с периодом d, если m % d == 0 — эта пара строк экономит десятки строк альтернативной реализации.

Три алгоритма поиска подстроки из этого урока — не три конкурента, из которых нужно раз и навсегда выбрать «лучший», а три разных ответа на один и тот же вопрос «как не делать одну и ту же работу дважды»: КМП использует структуру самого паттерна, Рабин-Карп превращает сравнение символов в сравнение чисел, а расширение от центра при поиске палиндромов переиспользует уже подтверждённую симметрию. Тот же принцип — искать, какая информация уже вычислена, и использовать её повторно вместо пересчёта с нуля, — снова и снова будет всплывать в оставшейся части курса, от вычислительной геометрии в следующем уроке до куда более сложных структур данных для текста. А в практике машинного обучения именно эти алгоритмы стоят за той секундой, которая уходит на превращение сырого текстового датасета в аккуратные, очищенные и токенизированные данные, готовые к обучению модели.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку

💬 Нашёл ошибку или есть вопрос по уроку? Написать в Telegram →