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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Понятно, что если образец <tex> P </tex> входит в строку <tex> S </tex>, то он является префиксом какого-нибудь ее суффикса. Если вхождений несколько, то в суффиксном массиве <tex> sufArray </tex> они будут находиться рядом друг с другом. Получается, что задача сводится к бинарному поиску в упорядоченном массиве. <br>
 
Понятно, что если образец <tex> P </tex> входит в строку <tex> S </tex>, то он является префиксом какого-нибудь ее суффикса. Если вхождений несколько, то в суффиксном массиве <tex> sufArray </tex> они будут находиться рядом друг с другом. Получается, что задача сводится к бинарному поиску в упорядоченном массиве. <br>
  
Пусть <tex> length </tex> - длина строки <tex> S </tex>. Тогда на первом шаге сравниваем суффикс <tex> sufArray[length / 2] </tex> и образец <tex> P </tex> по первому символу. Если первый элемент суффикса лексикографически больше, то необходимо идти в левую половину <tex> sufArray </tex>, иначе в правую. На следующем шаге аналогично проверяем суффикс по середине от половины суффискного массива, затем от четверти и так далее. В результате проделанной работы получим левую и правую границы <tex> L </tex> и <tex> R </tex> соответственно, в которых необходимо вести поиск.
+
Определим границы, в которых лежат вхождения. Пусть <tex> |S| </tex> - длина строки <tex> S </tex>. Тогда на первом шаге сравниваем суффикс <tex> sufArray[|S| / 2] </tex> и образец <tex> P </tex>. Если суффикс лексикографически больше, то необходимо идти в левую половину <tex> sufArray </tex>, иначе в правую. На следующем шаге аналогично проверяем суффикс по середине от половины суффискного массива, затем от четверти и так далее. В результате проделанной работы получим левую и правую границы <tex> L </tex> и <tex> R </tex> соответственно. В этих границах и лежат вхождения образца <tex> P </tex> в строку <tex> S </tex>. <br>
 +
Время лексикографического сравнения образца <tex> P </tex> с суффиксом <tex> S </tex> равно длине их общего префикса и не превышает <tex> |S| </tex>. Поэтому время работы алгоритма равно <tex> O(|S|log|S|).

Версия 05:20, 1 мая 2011

Пусть у нас есть образец [math] P [/math], строка [math] S [/math] и суффиксный массив [math] sufArray [/math]. Мы хотим найти все вхождения данного образца в данную строку. Существует несколько методов решения данной задачи.

Решение при помощи бинарного поиска

Понятно, что если образец [math] P [/math] входит в строку [math] S [/math], то он является префиксом какого-нибудь ее суффикса. Если вхождений несколько, то в суффиксном массиве [math] sufArray [/math] они будут находиться рядом друг с другом. Получается, что задача сводится к бинарному поиску в упорядоченном массиве.

Определим границы, в которых лежат вхождения. Пусть [math] |S| [/math] - длина строки [math] S [/math]. Тогда на первом шаге сравниваем суффикс [math] sufArray[|S| / 2] [/math] и образец [math] P [/math]. Если суффикс лексикографически больше, то необходимо идти в левую половину [math] sufArray [/math], иначе в правую. На следующем шаге аналогично проверяем суффикс по середине от половины суффискного массива, затем от четверти и так далее. В результате проделанной работы получим левую и правую границы [math] L [/math] и [math] R [/math] соответственно. В этих границах и лежат вхождения образца [math] P [/math] в строку [math] S [/math].
Время лексикографического сравнения образца [math] P [/math] с суффиксом [math] S [/math] равно длине их общего префикса и не превышает [math] |S| [/math]. Поэтому время работы алгоритма равно <tex> O(|S|log|S|).