Поиск в строке: от наивного цикла к KMP и автоматам

Ctrl+F в редакторе, grep по гигабайту логов, фильтр запрещённых слов в чате, поиск сигнатуры вируса в файле: всё это одна задача. Дан текст длины n и образец длины m, найди вхождения. JS отвечает на неё одним вызовом text.indexOf(pattern), и 95% времени этого достаточно. Урок про оставшиеся 5% и про то, что у indexOf, grep и regex-движка под капотом три разные идеи, каждая из которых стоит того, чтобы понять её один раз и навсегда.

По дороге мы переиспользуем два инструмента из прошлых уроков: хеши из урока про алгоритмы и конечные автоматы, которые ты видел в уроке про моделирование, только теперь автомат будет не моделью домена, а движком поиска.

Карта урока

1. Наивный поиск: почему он хорош и где его худший случай.
2. Префикс-функция и KMP: не выбрасывай то, что уже прочитал.
3. Boyer-Moore: можно сравнивать меньше, чем n символов.
4. Rabin-Karp: rolling hash и поиск без сравнения строк.
5. Поиск как конечный автомат: мост к regex-движкам.
6. Бор и Aho-Corasick: тысяча образцов за один проход.

Раздел 1 · Наивный поиск

Идея словами

Самое честное решение: приложить образец к каждой позиции текста и сравнить посимвольно.

const naiveSearch = (text, pattern) => {
  const found = [];
  for (let i = 0; i + pattern.length <= text.length; i++) {
    let j = 0;
    while (j < pattern.length && text[i + j] === pattern[j]) j++;
    if (j === pattern.length) found.push(i);
  }
  return found;
};

На обычных текстах это быстро: несовпадение почти всегда случается на первом-втором символе, и средняя сложность близка к O(n). Худший случай выглядит искусственно, но встречается в жизни (ДНК, бинарные данные, атаки на вход): текст aaaaaaaaab, образец aaab. Каждая позиция совпадает почти до конца и срывается на последнем символе:

текст:    a a a a a a a b
образец:  a a a b           сравнили 4, сорвались
            a a a b         снова 4
              a a a b       и снова

Получается O(n·m) сравнений. Обрати внимание на главное расточительство: сорвавшись, мы возвращаем j к нулю и заново читаем символы, которые уже видели. Вся следующая секция выжимает из этого наблюдения алгоритм.

Что взять с собой

Наивный поиск это O(n·m) в худшем случае, и его слабость не в скорости сравнения, а в том, что после срыва он забывает всё прочитанное.

Раздел 2 · Префикс-функция и KMP

Сцена

Ты читаешь текст слева направо, образец абраабр совпал до позиции 6 и сорвался. Стоп. Ты только что прочитал абраабр без последнего символа, то есть знаешь о тексте всё. Зачем возвращаться и перечитывать? Вопрос только один: с какого места образца продолжить сравнение. Ответ на него можно посчитать заранее, по самому образцу, и это весь KMP.

Идея словами

Ключевое понятие: префикс-функция. Для каждой позиции образца она отвечает: какой самый длинный префикс образца заканчивается прямо здесь? Если мы сорвались после k совпавших символов, то перед нами в тексте лежит префикс образца длины k, и pi[k - 1] говорит, сколько из него уже совпадает с началом образца. Туда и откатываемся, не двигая указатель по тексту назад.

const prefixFunction = (s) => {
  const pi = new Array(s.length).fill(0);
  for (let i = 1; i < s.length; i++) {
    let k = pi[i - 1];
    while (k > 0 && s[i] !== s[k]) k = pi[k - 1];
    if (s[i] === s[k]) k++;
    pi[i] = k;
  }
  return pi;
};

const kmpSearch = (text, pattern) => {
  const pi = prefixFunction(pattern);
  const found = [];
  let k = 0; // сколько символов образца сейчас совпало
  for (let i = 0; i < text.length; i++) {
    while (k > 0 && text[i] !== pattern[k]) k = pi[k - 1];
    if (text[i] === pattern[k]) k++;
    if (k === pattern.length) {
      found.push(i - pattern.length + 1);
      k = pi[k - 1]; // продолжаем искать перекрывающиеся вхождения
    }
  }
  return found;
};

Почему это O(n + m): указатель i по тексту никогда не идёт назад, а счётчик k суммарно не может уменьшаться больше, чем увеличивался, и вырасти он может максимум n раз. Амортизация, ровно как у динамического массива из урока про алгоритмы.

Та же идея в потоковой форме: KMP не нужен весь текст сразу, он ест по символу и хранит одно число k. Поэтому он отлично живёт поверх стрима, без буферизации гигабайта в память.

Что взять с собой

KMP это наивный поиск, который после срыва не перечитывает текст, а по заранее посчитанной префикс-функции знает, сколько уже совпало. Гарантия O(n + m), указатель по тексту только вперёд, годен для стримов.