Алгоритм поиска подстроки в строке с помощью суффиксного массива

Рассмотрим такую задачу: у нас есть образец [math] p [/math], строка [math] s [/math], суффиксный массив [math] array [/math], построенный для строки [math] s [/math]. Необходимо найти все вхождения образца [math] p [/math] в строку [math] s [/math].

Для наглядности рассмотрим такой пример: образец iss , строка mississippi .
Вот суффиксный массив для данной строки:

#	суффикс	номер суффикса
1	i	11
2	ippi	8
3	issippi	5
4	ississippi	2
5	mississippi	1
6	pi	10
7	ppi	9
8	sippi	7
9	sissippi	4
10	ssippi	6
11	ssissippi	3

Способы поиска

Простейший поиск подстроки

Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и бинарным поиском по суффиксному массиву (массив у нас отсортирован) найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца. Бинарный поиск работает за время равное [math] O(log|s|) [/math], а сравнение суффикса с образцом не может превышать длины образца. Таким образом время работы алгоритмы [math] O(|p|log|s|)[/math].
В примере поиск будет выглядеть так:

образец	iss	iss	iss
	i	i	i
	ippi	ippi	ippi
	issippi	issippi	issippi
	ississippi	ississippi	ississippi
	mississippi	mississippi	mississippi
	pi	pi	pi
	ppi	ppi	ppi
	sippi	sippi	sippi
	sissippi	sissippi	sissippi
	ssippi	ssippi	ssippi
	ssissippi	ssissippi	ssissippi

В примере показано, какие суффиксы на каждом шаге алгоритма удовлетворяют нашему образцу: на [math] i [/math]-ом шаге суффикс является подходящим, если [math] i [/math] его первых символов совпадают с [math] i [/math] первыми символами образца. Каждый шаг к рассмотрению добавляется лишь одна буква. В графе "образец" розовым цветом выделен префикс образца, который ищется на данном шаге, а под образцом располагаются суффиксы строки, префиксы которых выделены розовым цветом, если на данном шаге суффикс подходит.
Как видно из примера образцу удовлетворяют суффиксы 3 и 4, начинающиеся на 5 и 2 позициях в строке соответственно.

Псевдокод

Поиск диапазона

/*p - образец
n - длина образца
left - левая граница диапазона // изначально равна единице
right - правая граница диапазона // изначально равна длине строки
lh - вспомогательная переменная для определения левой границы диапазона  
rg - вспомогательная переменная для определения правой границы диапазона
find - функция уточнения диапазона
элементы строк и массивов нумеруются с единицы*/
for i = 1 to n {
  lh = n + 1
  rh = 0
  find(left, right, i)
  left = lh
  right = rh
}
if (left != 0 && right != n + 1) { // если диапазон не пуст
  yield left // вывод левой границы диапазона 
  yield right // вывод правой границы диапазона
} else
 yield "No matches" // вывод информации об отсутствии вхождений

Бинарный поиск для уточнения диапазона - функция find(l, r, k)

/*l - левая граница диапазона при поиске
r - правая граница диапазона при поиске
k - номер символа образца, с которым происходит проверка на данном шаге
s - строка
length - длина строки
array - суффиксный массив
x - индекс, стоящий по середине между l и r*/
if (l > r)
  return
x = (l + r) / 2
if (array[x] + k - 1 <= length){
  if (s[array[x] + k - 1] == p[k]){
    if (x < lh)
      lh = x
    if (x > rh)
      rh = x
    find(l, x - 1, k)
    find(x + 1, r, k)
  } else { 
  if (s[array[x] + k - 1] > p[k]) {
    find(l, x - 1, k)
  } else {
  if (s[array[x] + k - 1] < p[k]) {
    find(x + 1, r, k)
  }
} else { 
  find(l, x - 1, k)
  find(x + 1, r, k)
}

Более быстрый поиск

На [math] i [/math]-ом шаге алгоритма мы определяем диапазон, в котором [math] i [/math] первых символов образца и суффиксов диапазона совпадают. На самом деле нам не обязательно на каждом шаге проверять лишь один новый символ. Воспользуемся [math] lcp [/math](longest common prefix).
Пусть левая и правая границы нашего диапазона на каком-то шаге - это [math] L [/math] и [math] R [/math] соответственно. Допустим, что мы знаем длину общего префикса образца с суффиксами, лежащими на краях текущего диапазона: [math] l [/math] - общий префикс образца и суффикса с левого края ([math] l = lcp(p, array[L]) [/math]), а [math] r [/math] - общий префикс образца и суффикса с правого края ([math] r = lcp(p, array[R]) [/math]). Будем поддерживать [math] l [/math] и [math] r [/math] после каждого уточнения границ диапазона.
Для каждой пары суффиксов внутри текущего диапазона их lcp не меньше, чем минимум из [math] l [/math] и [math] r [/math], то есть общий префикс образца и любого суффикса внутри диапазона не меньше [math] m = min(l,r) [/math]. Значит [math] m [/math] символов можно пропускать сразу, зная, что они совпадают в любом случае, и сравнивать уже [math] m + 1 [/math] символ.

В худшем случае, конечно, ничего мы от этого не выиграем: если искомый элемент находится на краю массива, но соседи совсем не похожи по [math] lcp [/math], то [math] r [/math] (или [math] l [/math]) будет мало каждый раз, [math] m [/math] будет тоже мало, что сведет оптимизацию на нет. Таким образом в наихудшем случае результат будет прежним [math] O(|p|log|s|) [/math], но в среднем [math] O(|p| + log|s|) [/math].

Литература

• http://habrahabr.ru/blogs/algorithm/115346/