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

Общая постановка задачи

Пусть дан образец Needle длиной n и строка Haystack. Требуется найти такой индекс i, что:

$\forall l\in {\overline {0,n-1}}\ haystack_{i+l}=needle_{l}$

Либо, если такого индекса не существует, вернуть число, которое не может быть интерпретировано как индекс, например, отрицательное.

Наивный алгоритм

Идём вперёд по строке и на каждой итерации проверяем, совпадают ли следующие n символов с Needle.

 let naive_search haystack needle =
  let needle_len = String.length needle in
  let search_end = String.length haystack - needle_len in
  let rec search i =
   if i > search_end then -1 else
   if (String.sub haystack i needle_len) = needle then i else
   search (succ i) in
  search 0

Как нетрудно заметить, в худшем случае на каждой итерации нужно $|needle|-1$ сравнений, всего производится $|haystack|-|needle|$ итераций, поэтому наибольшее количество сравнений, которое, возможно, придётся произвести - это $(|haystack|-|needle|)*(|needle|-1)$, что соответствует $O(|haystack|*|needle|)$.

Алгоритм Рабина-Карпа

Хэш-функции

Вообще говоря, хэш-функцией называется функция $[hash\colon 'a\to int]$, дающая более-менее равномерное распределение результатов. Кстати, такая функция представлена в библеотеке OCaml'а. Но в сейчас нас интересует более узкое понятие: хэш-функция строки. Самый простой способ её реализовать - это просто просуммировать коды всех символов.

Описание алгоритма

Вычислим хэш-функцию от needle и от первых n символов haystack и сравним их. Если совпали, произведём обыкновенное сравнение. Если нет, сдвинем позицию проверки вправо на единицу, вычтем из значения хэш-функции хэш первого символа и прибавим хэш n+1-го. Повторить...

 let hash s =
  let sum = ref 0 in
  for i = 0 to pred (String.length s) do
   sum := !sum + (int_of_char s.[i]);
  done; !sum
 
 let rabin_karp haystack needle =
  let haystack_len = String.length haystack
  and needle_len = String.length needle in
  let search_end = haystack_len - needle_len in
  if search_end < 0 then -1 else
  let needle_hash = hash needle in
  let rec search i h =
   if (i > search_end) then -1 else
   if (h = needle_hash) && ((String.sub haystack i needle_len) = needle) then i else
   if (i = search_end) then -1 else search (succ i)
    (h - (int_of_char haystack.[i]) + (int_of_char haystack.[i + needle_len])) in
  search 0 (hash (String.sub haystack 0 needle_len))

Алгоритм Кнута-Морриса-Пратта

Общее описание

Рассмотрим сравнение строк на позиции i, где образец $Needle[0,m-1]$ сопоставляется с частью текста $Haystack[i,i+m-1]$. Предположим, что первое несовпадение произошло между $Haystack[i+j]$ и $Needle[j]$, где $1<j<m$. Тогда $Haystack[i,i+j-1]=Needle[0,j-1]=P$ и $a=Haystack[i+j]\neq Needle[j]=b$.

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца P сойдется с каким-нибудь суффиксом (подсловом) текста P. Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки P.

 let self_repeat s =
  let len = String.length s in
  let rec sr i =
   if (String.sub s 0 i) = (String.sub s (len - i) i) then i else sr (pred i) in
  if len = 0 then 0 else sr (pred (String.length s))

Таким образом, если при сравнении несовпадение произошло в позиции i, можно сдвигать текущий указатель начала сравнения вперёд не на единицу, а на префикс-функцию от подстроки $Needle[0,i-1]$.

Классический вариант

 let kmp haystack needle =
  let build_backw s =
   Array.init (String.length s) (fun i -> self_repeat (String.sub s 0 i)) in
  let backw = build_backw needle
  and needle_len = String.length needle
  and haystack_len = String.length haystack in
  let rec apply i n =
   if n = needle_len then (i - needle_len) else
   if i = haystack_len then (-1) else
   if haystack.[i] <> needle.[n] then
    if n = 0 then apply (succ i) 0 else
                  apply i backw.(n) else
    apply (succ i) (succ n) in
  apply 0 0

Автоматный вариант

 let build_fsm needle =
  let needle_len = String.length needle in
  Array.init 256 (fun ch -> Array.init needle_len (fun len ->
   let c = char_of_int ch in
   if needle.[len] = c then succ len else
   self_repeat ((String.sub needle 0 len) ^ (String.make 1 c))))
 
 let automation haystack needle =
  let needle_len = String.length needle
  and haystack_len = String.length haystack
  and auto = build_fsm needle in
  let rec apply i n =
   if n = needle_len then (i - needle_len) else
   if i = haystack_len then (-1) else
   find (succ i) (auto.(int_of_char haystack.[i]).(n)) in
  apply 0 0

Разница между этими двумя вариантами заключается лишь в том, что автомат строится дольше, чем массив откатов (причём в 256 раз), зато его применение несколько эффективнее, так как массив откатов учитывает все совпавшие символы, а автомат, кроме них, ещё один - тот, на котором произошло несоответствие.