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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 68: Строка 68:
 
  |-
 
  |-
 
  |
 
  |
  |i
+
  |'''''i'''''
 
  |i
 
  |i
 
  |i
 
  |i
 
  |-
 
  |-
 
  |
 
  |
  |ippi
+
  |'''''i'''ppi''
 
  |ippi
 
  |ippi
 
  |ippi
 
  |ippi
 
  |-
 
  |-
 
  |
 
  |
  |issippi
+
  |'''''i'''ssippi''
  |issippi
+
  |'''''is'''sippi''
  |issippi
+
  |'''''iss'''ippi''
 
  |-
 
  |-
 
  |
 
  |
  |ississippi
+
  |'''''i'''ssissippi''
  |ississippi
+
  |'''''is'''sissippi''
  |ississippi
+
  |'''''iss'''issippi''
 
  |-
 
  |-
 
  |
 
  |

Версия 01:53, 8 мая 2011

Рассмотрим такую задачу: у нас есть образец [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