Строковые алгоритмы (KMP, Rabin-Karp, Z, Aho-Corasick)

Строковые алгоритмы — это фундамент для задач, где нужно искать паттерны, сравнивать подстроки или извлекать структурную информацию из текста. Ключевая идея всех эффективных строковых алгоритмов: не пересматривать то, что уже обработано. Наивное сравнение подстроки требует O(n·m) операций, специализированные алгоритмы снижают сложность до O(n+m) за счёт предварительной обработки паттерна или текста.

Когда применять

• KMP — поиск одной подстроки в тексте, гарантия O(n+m) в худшем случае.
• Rabin-Karp — поиск анаграмм, повторяющихся подстрок, multiple-pattern (через хеш-таблицу хешей).
• Z-function — те же задачи, что KMP, но иногда проще в реализации; задачи с периодичностью.
• Suffix Array + LCP — число различных подстрок, longest common substring двух строк, поиск паттерна за O(m log n).
• Aho-Corasick — поиск множества паттернов в одном тексте за один проход (антивирусы, IDS, фильтрация слов).
• Manacher — все палиндромные подстроки за O(n).

Идея

KMP (Knuth–Morris–Pratt) строит префикс-функцию (LPS array) для паттерна: lps[i] — длина максимального собственного префикса pattern[0..i], который также является его суффиксом. При несовпадении KMP не откатывает указатель паттерна к началу, а «телепортирует» его к позиции, указанной в LPS, не пересматривая символы текста повторно. Построение LPS — O(m), поиск — O(n).

Rabin-Karp использует rolling hash: полиномиальный хеш окна размером m в тексте, сравниваемый с хешем паттерна. При сдвиге окна хеш обновляется за O(1). При совпадении хешей — посимвольная проверка (из-за коллизий). Среднее O(n+m), худший O(n·m). Double hashing (два модуля) защищает от adversarial input.

Z-function для строки s вычисляет массив Z, где Z[i] — длина наибольшего префикса s, совпадающего с s[i..]. Для поиска паттерна строим pattern + '#' + text и смотрим, где Z[i] = |pattern|.

Suffix Array — индексы суффиксов, отсортированных лексикографически. Построение O(n log² n) doubling или O(n) через SA-IS. С LCP array (Kasai O(n)) решает: число различных подстрок (n(n+1)/2 - sum(LCP[i])), longest common substring двух строк, поиск подстроки за O(m log n).

Aho-Corasick — расширение KMP на множество паттернов. Trie всех паттернов + суффиксные ссылки (fail links), аналогичные KMP-префикс-функции. Поиск за O(n + |patterns| + matches).

Manacher находит все палиндромы за O(n) через симметрию уже найденных. Альтернатива — expand-from-center O(n²) или хеши + binary search O(n log n).

Реализация: KMP

Задача (strStr): вернуть первый индекс вхождения needle в haystack, иначе -1.

function buildLPS(pattern: string): number[] {
  const m = pattern.length;
  const lps = new Array(m).fill(0);
  let len = 0; // длина предыдущего longest prefix suffix

  for (let i = 1; i < m; i++) {
    while (len > 0 && pattern[i] !== pattern[len]) {
      len = lps[len - 1]; // откатываемся к меньшему border
    }
    if (pattern[i] === pattern[len]) len++;
    lps[i] = len;
  }
  return lps;
}

function strStr(haystack: string, needle: string): number {
  if (needle.length === 0) return 0;
  if (haystack.length < needle.length) return -1;

  const lps = buildLPS(needle);
  let i = 0; // указатель haystack
  let j = 0; // указатель needle

  while (i < haystack.length) {
    if (haystack[i] === needle[j]) {
      i++;
      j++;
      if (j === needle.length) return i - j; // нашли
    } else if (j !== 0) {
      j = lps[j - 1]; // откат без возврата i
    } else {
      i++;
    }
  }
  return -1;
}

Трассировка для haystack="ababcababa", needle="ababa"

LPS("ababa") = [0, 0, 1, 2, 3]
i=0..3: совпадение "abab" → j=4
i=4: 'c' != 'a' → j = lps[3] = 2 (откат к "ab")
i=4: 'c' != 'a' → j = lps[1] = 0
i=4: 'c' != 'a' → i=5
i=5..9: match "ababa" → return 5

Сложность: O(n + m) время, O(m) память. KMP не пересматривает символы текста (указатель i только растёт).

Реализация: Rabin-Karp / Find All Anagrams

Задача: найти все стартовые индексы анаграмм строки p в строке s.

Анаграмма = одинаковый мультисет символов. Используем sliding window + хеш частот букв (массив длины 26 для строчных латинских).

function findAnagrams(s: string, p: string): number[] {
  if (s.length < p.length) return [];

  const result: number[] = [];
  const pCount = new Array(26).fill(0);
  const sCount = new Array(26).fill(0);

  for (const ch of p) pCount[ch.charCodeAt(0) - 97]++;
  for (let i = 0; i < p.length; i++) sCount[s.charCodeAt(i) - 97]++;

  if (arraysEqual(pCount, sCount)) result.push(0);

  for (let i = p.length; i < s.length; i++) {
    sCount[s.charCodeAt(i) - 97]++;             // правый
    sCount[s.charCodeAt(i - p.length) - 97]--;  // левый
    if (arraysEqual(pCount, sCount)) result.push(i - p.length + 1);
  }

  return result;
}

function arraysEqual(a: number[], b: number[]): boolean {
  for (let i = 0; i < 26; i++) if (a[i] !== b[i]) return false;
  return true;
}

:::tip Оптимизация Вместо сравнения массивов каждый раз можно вести счётчик matches — число букв с совпадающими частотами. При сдвиге окна обновляем matches за O(1), проверка анаграммы — matches === 26. :::

Сложность: O(n) время (26·n операций), O(1) дополнительная память (массивы фиксированного размера).

Сложность строковых алгоритмов

Алгоритм	Препроцесс	Поиск	Память
KMP	O(m)	O(n)	O(m)
Rabin-Karp	O(m)	O(n+m) avg, O(nm) worst	O(1)
Z-function	O(m)	O(n)	O(n+m)
Suffix Array	O(n log² n)	O(m log n)	O(n)
Aho-Corasick	O(Σ|patterns|)	O(n + matches)	O(Σ|patterns| · σ)
Manacher	—	O(n)	O(n)

Типичные ошибки и подводные камни

• Hash collisions в Rabin-Karp: при совпадении хешей нужна посимвольная проверка, иначе ложное срабатывание.
• Выбор модуля: большое простое (10⁹+7) снижает коллизии, но не устраняет; double hashing даёт практическую надёжность.
• Empty pattern: обычная договорённость — пустой паттерн совпадает с любой позицией (вернуть 0).
• Overflow: в JS полиномиальный хеш на больших строках может выйти за Number.MAX_SAFE_INTEGER — модульная арифметика на каждой операции или BigInt.
• KMP LPS off-by-one: lps[i] < i всегда (собственный префикс), внимательно с индексацией.
• Suffix Array наивно O(n² log n) непригоден для больших n — нужны doubling или SA-IS.

Follow-up вопросы

• Как найти самую длинную повторяющуюся подстроку? Binary search по длине + Rabin-Karp: для каждой длины L проверяем, есть ли две подстроки длины L с одинаковым хешем. Альтернатива — Suffix Array + LCP, ответ — max(LCP).

• Почему KMP лучше Rabin-Karp для одной подстроки? KMP гарантирует O(n+m) в худшем случае; Rabin-Karp — O(n·m) при adversarial input (все хеши коллизионные). Но для «все анаграммы» или multi-pattern RK удобнее.

• Когда Aho-Corasick вместо множественных KMP? Когда нужно искать много паттернов (>100) в одном большом тексте: AC проходит текст один раз, k вызовов KMP — k раз.

• Как Suffix Array помогает посчитать число различных подстрок? Общее число подстрок — n(n+1)/2. Повторяющиеся — это LCP между соседними суффиксами. Различных = n(n+1)/2 - sum(LCP[i]).

• В чём разница между Suffix Tree и Suffix Automaton? Suffix Tree — дерево суффиксов (каждый путь от корня = суффикс). Suffix Automaton — минимальный DAG, распознающий все подстроки (компактнее). SA используют в сжатии и full-text индексах.

• Как индексировать миллиард строк для полнотекстового поиска? Inverted index (слово → список документов) + ranking (TF-IDF, BM25). Для подстрочного поиска — n-граммы или suffix array со сжатием. Так устроены Elasticsearch, Lucene, Sphinx.

Чеклист на собес

• Назови сложность ДО кода: O(n+m) для KMP, O(n) avg для RK.
• Уточни алфавит (ASCII / Unicode), регистр, длины.
• Для multi-pattern сразу думай об Aho-Corasick.
• Для палиндромов начни с expand-from-center O(n²); упомяни Manacher как next step.
• При rolling hash используй два модуля для безопасности от коллизий.
• Помни про edge cases: пустые строки, паттерн длиннее текста, повторяющиеся символы.