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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

# суффикс номер суффикса
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

Как видно из примера образцу удовлетворяют суффиксы 3 и 4, начинающиеся на 5 и 2 позициях в строке соответственно.

Псевдокод

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

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

Бинарный поиск для уточнения диапазона

/*l - левая граница диапазона при