Префикс-функция, КМП и конечные автоматы

К разделу

1. Префикс-функция

Определение. Для строки $s$ префикс-функция — это массив $\pi$, где $\pi [i]$ — максимальная длина собственного префикса подстроки $s[0..i]$, который совпадает с ее суффиксом. «Собственный» значит «не равный всей строке».

Пример для строки abacaba:

$i$	0	1	2	3	4	5	6
$s[i]$	a	b	a	c	a	b	a
$\pi [i]$	0	0	1	0	1	2	3

• $\pi [0]=0$: у строки из одного символа нет собственных префиксов (по определению значение не определено, то есть ставим 0)
• $\pi [2]=1$: в aba префикс a совпадает с суффиксом a.
• $\pi [3]=0$: c не совпадает ни с чем в начале.
• $\pi [6]=3$: в abacaba префикс aba совпадает с суффиксом aba, и это максимальное совпадение.

Отличие от Z-функции

Они родственные, но смотрят в разные стороны:

• $\pi [i]$ — про суффикс, заканчивающийся в позиции $i$ (смотрим назад);
• $z[i]$ — про подстроку, начинающуюся в позиции $i$ (смотрим вперед): сколько символов от $i$ совпадает с началом строки.

На abacaba в позиции 4 значение $z$ было бы $3$ (aba совпадает с началом), а $\pi$ там равно 1. Строятся они по-разному: Z-функция опирается на Z-блоки, а префикс-функция — на уже накопленное знание о строке.

Как строить за линейное время

Идем слева направо. Пусть $\pi [0..i-1]$ уже посчитано, и мы хотим найти $\pi [i]$.

1. Берем $j=\pi [i-1]$ — длину текущего «лучшего» префикса, совпадающего с суффиксом перед позицией $i$.
2. Сравниваем символ $s[j]$ (следующий за префиксом) и $s[i]$ (новый символ)
   • Равны -> префикс удлиняется: $\pi [i]=j+1$. Больше ничего делать не надо.
   • Не равны -> надо найти следующий по длине суффикс, который тоже является префиксом. Логика похожа на то, что было в Ахо-Корасике: «откусываем» от суффикса, пока не найдем тот, к которому можно дописать символ. Переходим $j=\pi [j-1]$ и повторяем сравнение. Если дошли до $j=0$ и $s[0]\ne s[i]$, то $\pi [i]=0$.

Почему прыжок на $\pi [j-1]$ корректен. Строка $s[0..j-1]$ равна суффиксу, заканчивающемуся перед $i$. Любой ее собственный суффикс, равный префиксу, — это одновременно суффикс всего куска перед $i$, равный префиксу $s$. А все такие длины как раз перечисляет цепочка $\pi [j-1],\pi [\pi [j-1]-1],\dots$ в порядке убывания. Мы перебираем кандидатов от самого длинного к самому короткому, поэтому первый подошедший — максимальный.

Пример с откатом. aabaaab:

$i$	0	1	2	3	4	5	6
$s[i]$	a	a	b	a	a	a	b
$\pi [i]$	0	1	0	1	2	2	3

В позиции 5 имеем $j=\pi [4]=2$, но $s[2]=\text{b}\ne \text{a}$. Откатываемся: $j=\pi [1]=1$, $s[1]=\text{a}=s[5]$, значит $\pi [5]=2$. Дальше b дописывается к префиксу aa: $\pi [6]=3$.

Код

def prefix_function(s: str) -> list[int]:
    n = len(s)
    p = [0] * n
    for i in range(1, n):          # p[0] не определено, начинаем с 1
        j = p[i - 1]
        while j > 0 and s[i] != s[j]:
            j = p[j - 1]           # прыжок к следующему подходящему суффиксу
        if s[i] == s[j]:
            j += 1
        p[i] = j
    return p

Замечания:

• Цикл while не бесконечный: $j$ строго убывает, а при $j=0$ цикл останавливается. Индекс $i$ в нем не меняется — мы подбираем длину префикса для одной и той же позиции.
• Сравниваем s[i] с s[j], а прыгаем по p[j - 1]. Здесь $j$ — это длина префикса, поэтому следующий за ним символ имеет индекс $j$, а последний символ самого префикса — $j-1$.

Сложность

Суммарно $O(n)$: $j$ растет не более чем на 1 за итерацию внешнего цикла, а каждый шаг while его уменьшает, поэтому всего шагов while не больше $n$ (амортизированный анализ).

---

2. Поиск подстроки

Задача. Даны паттерн $P$ и текст $S$. Найти все вхождения $P$ в $S$.

2.1. Решение через склейку

Строим строку $T=P+\mathrm{\#}+S$, где # — символ, которого нет ни в паттерне, ни в тексте (разделитель). Считаем префикс-функцию для всей $T$. Везде, где $\pi [i]=|P|$, в тексте заканчивается вхождение паттерна: префикс (то есть сам $P$) равен суффиксу.

Пример: $P=\text{aba}$, $S=\text{abacaba}$, строка aba#abacaba:

a b a # a b a c a b a
0 0 1 0 1 2 3 0 1 2 3

Тройки соответствуют вхождениям. Разделитель нужен, чтобы значения $\pi$ не «перелезли» за длину паттерна.

Решение работает за $O(|P|+|S|)$

2.2. Алгоритм Кнута–Морриса–Пратта

КМП строит префикс-функцию только для паттерна, а потом идет по тексту и использует ее как минимальный автомат

Два указателя:

• $i$ — позиция в тексте $S$ (просто идет слева направо);
• $j$ — сколько символов паттерна сейчас совпало (позиция в паттерне).

На каждом символе текста:

1. Пока $j>0$ и $S[i]\ne P[j]$ — откатываемся: $j=\pi [j-1]$. Мы не сбрасываемся на начало, а оставляем максимальный суффикс, который все еще является префиксом паттерна: потерять его раньше времени было бы неправильно.
2. Если $S[i]=P[j]$, то $j+=1$.
3. Если $j=|P|$, паттерн найден целиком: вхождение начинается в позиции $i-|P|+1$. Дальше нужно откатиться тем же способом ($j=\pi [j-1]$), чтобы найти перекрывающиеся вхождения.

def kmp(s: str, t: str) -> list[int]:
    """Все вхождения паттерна t в строку s (индексы начала)."""
    m = len(t)
    if m == 0:                      # пустой паттерн — искать нечего
        return []
    p = prefix_function(t)          # префикс-функция ТОЛЬКО по паттерну
    res = []
    j = 0
    for i, ch in enumerate(s):
        while j > 0 and ch != t[j]:
            j = p[j - 1]
        if ch == t[j]:
            j += 1
        if j == m:                  # дошли до конца паттерна
            res.append(i - m + 1)
            j = p[j - 1]            # откат, чтобы не потерять перекрывающиеся
    return res

Пример. $P=\text{aba}$ ($\pi =[0,0,1]$), $S=\text{abacababa}$:

Позиция $i$	Символ	Что происходит	$j$ после
0	a	совпало	1
1	b	совпало	2
2	a	совпало, вхождение с 0; откат $j=\pi [2]=1$	1
3	c	$c\ne b$, откат $j=\pi [0]=0$; $c\ne a$	0
4	a	совпало	1
5	b	совпало	2
6	a	совпало, вхождение с 4; откат	1
7	b	совпало (суффикс a не потерян)	2
8	a	совпало, вхождение с 6; откат	1

Вхождения: 0, 4, 6. Если бы после нахождения aba мы сбросились в начало, вхождение с 6 потерялось бы (a в конце первой aba — начало следующей).

2.3. Сложность

$O(|P|+|S|)$: префикс-функция паттерна считается за $O(|P|)$; в основном цикле $j$ растет не больше чем на 1 за символ текста, а откаты его только уменьшают, значит суммарно откатов не больше $|S|$.

Главное отличие от склейки: КМП не хранит префикс-функцию для всего текста — только $O(|P|)$ памяти, а текст можно читать потоком.

---

3. Автомат: ДКА для поиска подстроки

Детерминированный конечный автомат (ДКА) — это граф, в котором:

• есть начальное состояние (с него начинаем);
• есть терминальные (принимающие) состояния: попали в них — значит, строка подошла;
• из каждого состояния по каждому символу алфавита ведет ровно один переход.

Автомату на вход подается строка $S$, он читает ее символ за символом и переходит по ребрам. На практике ДКА обычно строят из регулярного выражения, а затем «прогоняют» через него строки.

3.1. Автомат, который ищет aba (только первое вхождение)

Состояние $k$ означает «совпало $k$ первых символов aba». Состояния 0, 1, 2, 3; терминальное — 3.

• Из 0: по a в 1, по b остаемся в 0.
• Из 1: по b в 2; по a (два a подряд) остаемся в 1: последняя a может быть началом ответа.
• Из 2: по a в 3 (нашли aba); по b (получилось abb) в 0: ни один суффикс не подходит как префикс.
• Из 3 (терминальное): мы замыкаем переходы на себя, чтобы автомат не «сломался», хотя можно оставить и так, чтобы ломался.

Такой автомат отвечает на вопрос «встречается ли aba вообще», но не скажет, где еще оно встречается: после попадания в терминальную вершину мы остаемся в ней, сколько бы букв ни пришло.

3.2. Автомат КМП — ищет все вхождения

Чтобы находить все вхождения, из терминальной вершины надо уметь откатываться:

• из 3 по b → в 2 (abab: суффикс ab — префикс паттерна);
• из 3 по a → в 1 (abaa: суффикс a — префикс паттерна).

То есть автомат из пункта 3.1 дополняем переходами, которые «подхватывают» суффикс, уже совпавший с началом паттерна. Это и есть автомат КМП.

Итого переходы:

Состояние	по a	по b
0	1	0
1	1	2
2	3	0
3 (терминальное)	1	2

3.3. Связь с алгоритмом КМП

Алгоритм КМП и автомат КМП — одно и то же, просто в разном представлении:

• в автомате хранятся все переходы по всему алфавиту
• в КМП мы упаковываем автомат в массив $\pi$ и храним только нужные переходы: переход вперед («совпало», $j\to j+1$) и «откат назад» по $\pi$, который дает максимальный суффикс, равный префиксу.

Вместо того чтобы сразу прыгнуть в нужное состояние по любой букве, КМП делает серию откатов $j\to \pi [j-1]\to \dots$ до подходящего состояния. Это сжатый автомат: он занимает $O(|P|)$ памяти вместо $O(|P||\mathrm{\Sigma }|)$, ценой того, что один символ текста может потребовать нескольких откатов (амортизированно все равно $O(1)$).

Префикс-функция в Ахо-Корасике и в КМП — родственные идеи: суффиксные ссылки Ахо-Корасика — это обобщение откатов по $\pi$ на бор из многих слов.