Материал из Викиконспекты
|
|
| Строка 1: |
Строка 1: |
| − | Пусть у нас есть образец <tex> P </tex>, строка <tex> S </tex> и [[Суффиксный массив|суффиксный массив]] <tex> sufArray </tex>. Мы хотим найти все вхождения данного образца в данную строку.
| |
| | | | |
| − | ==Решение при помощи бинарного поиска==
| |
| − |
| |
| − | Понятно, что если образец <tex> P </tex> входит в строку <tex> S </tex>, то он является префиксом какого-нибудь ее суффикса. Если вхождений несколько, то в суффиксном массиве <tex> sufArray </tex> они будут находиться рядом друг с другом. Получается, что задача сводится к бинарному поиску в упорядоченном массиве. <br>
| |
| − |
| |
| − | Определим границы, в которых лежат вхождения. На первом шаге сравниваем суффикс <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> |P| </tex>. Поэтому время работы алгоритма равно <tex> O(|P|log|S|) </tex>.
| |
| − |
| |
| − | ==Улучшение бинарного поиска==
| |
| − |
| |
| − | При двоичном поиске обозначим левую и правую границы текущего интервала как <tex> L </tex> и <tex> R </tex> соответственно. Изначально <tex> L = 0 </tex>, <tex> R = |S| - 1 </tex>. На каждой итерации будем сравнивать образец <tex> P </tex> с суффиксом <tex> sufArray[(L + R) / 2] </tex>. Обозначим за <tex> left </tex> длину общего префикса <tex> P </tex> и <tex> sufArray[L] </tex>, а за <tex> right </tex> длину общего префикса <tex> P </tex> и <tex> sufArray[R] </tex>. Также обозначим за <tex> minRange </tex> минимум из <tex> left </tex> и <tex> right </tex>. Значение <tex> minRange </tex> будем поддерживать на каждой итерации двоичного поиска. Теперь, зная <tex> minRange </tex>, можно начинать сравнение образца <tex> P </tex> с суффиксом <tex> sufArray[(L + R) / 2] </tex>, начиная с <tex> minRange + 1 </tex> символа. Это возможно, так как для любого суффикса из нашей границы от <tex> L </tex> до <tex> R </tex> первые <tex> minRange </tex> символов совпадают. Если бы это было не так, то в суффиксном массиве в границе от <tex> L </tex> до <tex> R </tex> были бы суффиксы, которые сначала имеют <tex> minRange </tex> совпадений, затем не имеют, а затем снова имеют, что говорит о неправильном построении суффиксного массива. <br>
| |
| − | При таком поиске время работы равно <tex> O(|P| + log|S|) </tex>.
| |
Версия 00:42, 8 мая 2011
