Алгоритм поиска подстроки в строке с помощью суффиксного массива — различия между версиями
Vincent (обсуждение | вклад) |
Vincent (обсуждение | вклад) |
||
| Строка 123: | Строка 123: | ||
|} | |} | ||
Как видно из примера образцу удовлетворяют суффиксы 3 и 4, начинающиеся на 5 и 2 позициях в строке соответственно. | Как видно из примера образцу удовлетворяют суффиксы 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 - левая граница диапазона при | ||
Версия 02:33, 8 мая 2011
Рассмотрим такую задачу: у нас есть образец , строка , суффиксный массив , построенный для строки . Необходимо найти все вхождения образца в строку .
Для наглядности рассмотрим такой пример: образец , строка .
Вот суффиксный массив для данной строки:
| # | суффикс | номер суффикса |
| 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 |
Способы поиска
Простейший поиск подстроки
Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и бинарным поиском по суффиксному массиву (массив у нас отсортирован) найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца. Бинарный поиск работает за , а сравнение суффикса с образцом не может превышать длины образца. Таким образом время работы алгоритмы .
В примере поиск будет выглядеть так:
| образец | 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 - левая граница диапазона при
