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

Рассмотрим такую задачу: у нас есть образец [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] lcp [/math] (longest common prefix).
Пусть [math] L_p [/math] и [math] R_p [/math] - левая и правая границы диапазона ответов в суффиксном массиве [math] array [/math]. У любого суффикса в пределах этого диапазона есть префикс, который полностью совпадает с образцом.
Пусть [math] L [/math] - левая граница диапазона поиска (изначально равна 0), [math] R [/math] - правая граница диапазона поиска (изначально равна [math] |S| - 1 [/math]), а [math] M = (L + R) / 2 [/math].
Пусть [math] l = lcp(array[L], p) [/math], а [math] r = lcp(array[R], p) [/math]. В самом начале просто посчитаем [math] l [/math] и [math] r [/math] за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за [math] O(1) [/math].
Пусть [math] m_l = lcp(array[L], array[M]) [/math], а [math] m_r = lcp(array[M],array[R]) [/math]. Подсчет [math] m_l [/math] и [math] m_r [/math] можно производить за [math] O(1) [/math], если применять алгоритм Фарака-Колтона и Бендера. Любая пара суффиксов [math] array [/math] из диапазона [math] [L, M] [/math] имеет хотя бы [math] m_l [/math] совпадений в префиксах. Аналогично любая пара суффиксов [math] array [/math] из диапазона [math] [M, R] [/math] имеет хотя бы [math] m_r [/math] совпадений в префиксах.
Рассмотрим поиск левой границы диапазона ответов [math] L_p [/math].
Сразу проверим образец с суффиксами по краям исходного диапазона поиска [math] L [/math] и [math] R [/math]: если образец лексикографически больше последнего суффикса [math] array [/math] или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить.
[math] L_p [/math] ищется при помощи бинарного поиска по суффиксному массиву [math] array [/math]. На каждом шаге поиска нам надо определять, на каком отрезке [math] [L, M] [/math] или [math] [M, R] [/math] надо продолжать поиск границы [math] L_p [/math]. Каждую итерацию бинарного поиска будем сравнивать [math] l [/math] и [math] r [/math]. Если [math] l \ge r [/math], то возможно одно из трех:

• 1. [math] m_l = l [/math]. Это означает, что у каждого суффикса из [math] [L, M] [/math] есть хотя бы [math] l [/math] совпадений с образцом. Проверим суффикс в позиции [math] M [/math], так как с ним совпадений у образца может получиться больше. Начнем сравнивать суффикс в позиции [math] M [/math] начиная с [math] l [/math]-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге [math] k [/math] получим несоответствие. В первом случае [math] R = M [/math] и [math] r = |p| [/math], так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ [math] l + k [/math] у образца меньше, чем у суффикса, то [math] R = M [/math] и [math] r = l + k [/math], иначе [math] L = M [/math] и [math] l = l + k [/math].
  
• 2. [math] m_l \gt l [/math]. Это означает, что каждая пара суффиксов из диапазона [math] [L, M] [/math] имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне [math] [M, R] [/math]. Значение [math] l [/math] при этом не меняется, а [math] L = M [/math].
  
• 3. [math] m_l \lt l [/math]. Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции [math] M [/math]. Очевидно, что поиск надо продолжать между [math] L [/math] и [math] M [/math], то есть [math] R = M [/math], а новое значение [math] r = m_l [/math].
  

Если [math] l \lt r [/math], то действия аналогичны:

• 1. [math] m_r = r [/math]. Это означает, что у каждого суффикса из [math] [M, R] [/math] есть хотя бы [math] r [/math] совпадений с образцом. Проверим суффикс в позиции [math] M [/math], так как с ним совпадений у образца может получиться больше. Начнем сравнивать суффикс в позиции [math] M [/math] начиная с [math] r [/math]-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге [math] k [/math] получим несоответствие. В первом случае [math] R = M [/math] и [math] r = |p| [/math], так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ [math] r + k [/math] у образца меньше, чем у суффикса, то [math] R = M [/math] и [math] r = r + k [/math], иначе [math] L = M [/math] и [math] l = r + k [/math].
  
• 2. [math] m_r \gt r [/math]. Это означает, что каждая пара суффиксов из диапазона [math] [M, R] [/math] имеет между собой больше совпадений, чем суффикс с правого края с образцом, поэтому продолжим поиск в диапазоне [math] [L, M] [/math]. Значение [math] r [/math] при этом не меняется, а [math] R = M [/math].
  
• 3. [math] m_r \lt r [/math]. Это означает, что совпадений у суффикса с правого края диапазона поиска с образцом больше, чем у суффикса в позиции [math] M [/math]. Очевидно, что поиск надо продолжать между [math] M [/math] и [math] R [/math], то есть [math] L = M [/math], а новое значение [math] l = m_r [/math].
  

Бинарный поиск будет работать до тех пор, пока [math] R - L \gt 1 [/math]. После этого можно присвоить левой границе диапазона ответов [math] L_p = R [/math] и переходить к поиску правой границы диапазона ответов [math] R_p [/math].
Рассуждения при поиске [math] R_p [/math] аналогичны, только нужно не забыть изменить границы поиска на изначальные [math] L = 0 [/math] и [math] R = |s| - 1 [/math].
Таким образом часть бинарного поиска мы сделаем при сравнении нескольких [math] lcp [/math] между собой(каждое за [math] O(1) [/math]), а если дойдет до сравнения символов, то любой символ [math] p [/math] сравнивается не более одного раза(при сравнении мы берем [math] max(l, r) [/math], а значит никогда не возвращаемся назад). В самом начале мы посчитали [math] l [/math] и [math] r [/math] за [math] O(p) [/math]. В итоге получаем сложность алгоритма [math] O(p + log(s)) [/math]. Правда нужен предподсчет, чтобы можно было брать [math] lcp [/math] для двух любых суффиксов [math] array [/math] за [math] O(1) [/math].

Разбор случаев

Условные обозначения:

• 1. Черная вертикальная линия на рисунке обозначает [math] lcp [/math] от [math] i [/math]-го суффикса суффиксного массива [math] array [/math] и образца [math] p [/math]. Чем линия длиннее, тем совпадений символов больше.
• 2. L, M и R - то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает [math] l [/math], аналогично, самая правая черная вертикальная линия на каждом рисунке означает [math] r [/math]. Переменная [math] m_l [/math] - это [math] lcp [/math] в суффиксном массиве на промежутке [math] [L, M] [/math]. Переменная [math] m_r [/math] - это [math] lcp [/math] в суффиксном массиве на промежутке [math] [M, R] [/math].
• 3. Серым цветом выделен [math] lcp [/math] в суффиксном массиве на рассматриваемом промежутке.

Простой пример для образца aaa на отсортированных суффиксах строки aaaaaa . Жирным выделены буквы, которые на рисунках будут представлены черными линиями (совпадения с образцом), а серым — совпадения суффиксов друг с другом на промежутке [math] [M, R] [/math].

Дальнейший разбор случаев никак не связан со строкой aaaaaa и образцом aaa .
Ищется левая граница ответов [math] L_p [/math].
Разберем случай [math] l \ge r [/math]. Возможны три варианта:

• a) [math] l \lt m_l [/math]. Сдвигаем [math] L [/math] в [math] M [/math]. Значение [math] l [/math] не изменяется.
• b) [math] l = m_l [/math]. Считаем [math] lcp [/math] для образца и суффикса, стоящего в позиции [math] M [/math], начиная с позиции [math] l [/math].
• с) [math] l \gt m_l [/math]. Сдвигаем [math] R [/math] в [math] M [/math], [math] r = m_l [/math].

Разберем случай при [math] l \lt r [/math]. Также возможны три варианта:

• a) [math] r \lt m_r [/math]. Сдвигаем [math] R [/math] в [math] M [/math]. Значение [math] r [/math] не изменяется.
• b) [math] r = m_r [/math]. Считаем [math] lcp [/math] для образца и суффикса, стоящего в позиции [math] M [/math], начиная с позиции [math] r [/math].
• с) [math] r \gt m_r [/math]. Сдвигаем [math] L [/math] в [math] M [/math], [math] l = m_r [/math].

Псевдокод

Поиск левой границы ответов [math] L_p [/math].

/*
Массивы и строки нумеруются с нуля.
Сравнения <[math]_z [/math] ,  >[math]_z [/math] ,  =[math]_z [/math] , <=[math]_z [/math] , >=[math]_z [/math] означают
  лексикографическое сравнение двух строк по их первым z символам.
Сравнения < , > , == , <= , >= при применении к строкам
  означают полное лексикографическое сравнение строк.
Функция lcp[math]_z[/math](s, p) ищет количество совпадений символов
  строк s и p начиная с позиции z. 
n - длина строки s.
w - длина строки p.
В алгоритме используются переменные, введенные выше в разделе "более быстрый поиск".
*/
l = lcp(p, s[array[0]]) 
r = lcp(p, s[array[n-1]])
if (l == w or p < s[array[0]])
  L[math]_p[/math] = 0 
else if (p > s[array[n-1])
  L[math]_p[/math] = n
else {
  L = 0
  R = n - 1
  while (R - L > 1) do {
    M = (L + R)/2
    m[math]_l[/math] = lcp(array[L],array[M])
    m[math]_r[/math] = lcp(array[M],array[R])
    if (l >= r)
      if (m[math]_l[/math] >= l)
        m = l + lcp[math]_l[/math](s[array[M]], p)
      else
        m = m[math]_l[/math]
    else
      if (m[math]_r[/math] >= r)
        m = r + lcp[math]_r[/math](s[array[M]], p)
      else
        m = m[math]_r[/math]
    if (m == w || p <=[math]_m[/math] s[array[M]]){
      R = M
      r = m
    } else {
      L = M
      l = m
    }
  }
  L[math]_p[/math] = R 
}

Литература

• http://habrahabr.ru/blogs/algorithm/115346/
• U. Manber and G. Mayers. "Suffix arrays: A new method for on-line string searches"