1632
правки
Изменения
м
yield print left yield print right
yield print "No matches";
'''=== Условные обозначения'''===
'''=== Алгоритм:'''===
У Если диапазон ответов не пустой, то у любого суффикса в пределах диапазона от <tex> L_p </tex> до <tex> R_p </tex> ответов есть префикс, который полностью совпадает с образцом.
'''Рисунки:'''
* Черная вертикальная линия на рисунке обозначает <tex>\mathtt {lcp} </tex> от <tex> i </tex>-го суффикса суффиксного массива <tex> array </tex> и образца <tex> p </tex>. Чем линия длиннее, тем совпадений символов больше.
* <tex> L </tex>, <tex> M </tex> и <tex> R </tex> {{---}} то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает <tex> l </tex>, аналогично, самая правая черная вертикальная линия на каждом рисунке означает <tex> r </tex>. Переменная <tex> m_l </tex> {{---}} это <tex>\mathtt {lcp} </tex> в суффиксном массиве на промежутке <tex> [L, M] </tex>. Переменная <tex> m_r </tex> {{---}} это <tex>\mathtt {lcp} </tex> в суффиксном массиве на промежутке <tex> [M, R] </tex>.
* Серым цветом выделен <tex>\mathtt {lcp} </tex> в суффиксном массиве на рассматриваемом промежутке.
[[Файл:left.png]]
[[ФайлИллюстраци возможных случаев при <tex> l \geqslant r </tex>:Right2.png]]
Бинарный поиск будет работать до тех пор, пока <tex> R - L > 1 </tex>. После этого можно присвоить левой границе диапазона ответов <tex> L_p = R </tex> и переходить к поиску правой границы диапазона ответов <tex> R_p </tex>[[Файл:left.png]]
Рассуждения Иллюстрации возможных случаев при поиске <tex> R_p l </tex> аналогичны, только нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 r </tex>.:
Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex>\mathtt {lcp} </tex> между собой(каждое за <tex> O(1) </tex>), а если дойдет до сравнения символов, то любой символ <tex> p </tex> сравнивается не более одного раза(при сравнении мы берем <tex>\mathtt {max}</tex><tex>(l, r) </tex>, а значит никогда не возвращаемся назад). В самом начале мы посчитали <tex> l </tex> и <tex> r </tex> за <tex> O(p) </tex>. В итоге получаем сложность алгоритма <tex> O(p + log(s)) </tex>. Правда нужен предподсчет, чтобы можно было брать <tex>\mathtt {lcp} </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>, начиная с позиции <tex> r </tex>[[Файл:Right2.png]]
L_p answer_left = 0
L_p answer_left = n
L_p answer_left = R
rollbackEdits.php mass rollback
Элементы строк нумеруются с единицы
'''function''' elementary_search(p: '''String''', s: '''String'''):
left = 0 <font color=darkgreen> // left, right {{---}} границы диапазона </font>
right = n <font color=darkgreen> // n {{---}} длина образца </font>
right = upper_bound(left, right, p[i], cmp (i) )
'''if''' (right - left > 0)
'''else'''
== Более быстрый поиск ==
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex>\mathtt {lcp} </tex> ([[Суффиксный массив#Применения|longest common prefix]]).
* <tex> L_p \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> и <tex> R_p \mathtt{answer} </tex>_<tex>\mathtt{right}</tex> {{---}} левая и правая границы диапазона ответов в суффиксном массиве <tex> array </tex>.,* <tex> L </tex> {{---}} левая граница текущего диапазона поиска (изначально равна <tex>0</tex>).,* <tex> R </tex> {{---}} правая граница текущего диапазона поиска (изначально равна <tex> |S| - 1 </tex>).,* <tex> M = (L + R) / 2 </tex>.{{---}} середина текущего диапазона поиска,* <tex> l = </tex><tex>\mathtt {lcp(array[L], p)} </tex>.{{---}} длина общего префикса образца и левого края текущего диапазона поиска,* <tex> r = </tex><tex>\mathtt {lcp(array[R], p)} </tex>.{{---}} длина общего префикса образца и правого края текущего диапазона поиска,* <tex> m_l = </tex><tex>\mathtt {lcp(array[L], array[M])} </tex>.{{---}} длина общего префикса середины текущего диапазона и левого края текущего диапазона поиска,* <tex> m_r = </tex><tex>\mathtt {lcp(array[M], array[R])} </tex>{{---}} длина общего префикса середины текущего диапазона и правого края текущего диапазона поиска.
В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное времяс помощью [[Алгоритм Касаи и др.|алгоритма Касаи, Арикавы, Аримуры, Ли и Парка]], а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>.
Подсчет <tex> m_l </tex> и <tex> m_r </tex> можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|алгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов <tex> array </tex> из диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах. Аналогично любая пара суффиксов <tex> array </tex> из диапазона <tex> [M, R] </tex> имеет хотя бы <tex> m_r </tex> совпадений в префиксах.
=== Поиск границ диапазона ответов ===
Рассмотрим поиск левой границы диапазона ответов <tex> L_p \mathtt{answer} </tex>_<tex>\mathtt{left}</tex>.
Сразу проверим образец с суффиксами по краям исходного диапазона поиска <tex> L </tex> и <tex> R </tex>: если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить.
<tex> L_p \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> ищется при помощи бинарного поиска по суффиксному массиву <tex> array </tex>. На каждом шаге поиска нам надо определять, на каком отрезке <tex> [L, M] </tex> или <tex> [M, R] </tex> надо продолжать поиск границы <tex> L_p \mathtt{answer} </tex>_<tex>\mathtt{left}</tex>. Каждую итерацию бинарного поиска будем сравнивать <tex> l </tex> и <tex> r </tex>. Если <tex> l \geqslant r </tex>, то возможно одно из трех:
# <tex> m_l > l </tex>. Это означает, что каждая пара суффиксов из диапазона <tex> [L, M] </tex> имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. Значение <tex> l </tex> при этом не меняется, а <tex> L = M </tex>.
# <tex> m_l = l </tex>. Это означает, что у каждого суффикса из <tex> [L, M] </tex> есть хотя бы <tex> l </tex> совпадений с образцом. Проверим суффикс в позиции <tex> M </tex>, так как с ним совпадений у образца может получиться больше. Начнем сравнивать суффикс в позиции <tex> M </tex> начиная с <tex> l </tex>-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге <tex> k </tex> получим несоответствие. В первом случае <tex> R = M </tex> и <tex> r = |p| </tex>, так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ <tex> l + k + 1 </tex> у образца меньше, чем у суффикса, то <tex> R = M </tex> и <tex> r = l + k + 1</tex>, иначе <tex> L = M </tex> и <tex> l = l + k + 1</tex>.
# <tex> m_l < l </tex>. Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> M </tex>. Очевидно, что поиск надо продолжать между <tex> L </tex> и <tex> M </tex>, то есть <tex> R = M </tex>, а новое значение <tex> r = m_l </tex>.
Если <tex> l < r </tex>, то действия аналогичны. Также три случая:
# <tex> m_r > r </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>. Значение <tex> r </tex> не изменяется.
# <tex> m_r = r </tex>. Считаем <tex>\mathtt {lcp} </tex> для образца и суффикса, стоящего в позиции <tex> M </tex>, начиная с позиции <tex> r </tex>.
# <tex> m_r < r </tex>. Сдвигаем <tex> L </tex> в <tex> M </tex>, <tex> l = m_r </tex>.
Бинарный поиск будет работать до тех пор, пока <tex> R - L > 1 </tex>. После этого можно присвоить левой границе диапазона ответов <tex> \mathtt{answer} </tex>_<tex>\mathtt{left} = R </tex> и переходить к поиску правой границы диапазона ответов <tex> \mathtt{answer} </tex>_<tex>\mathtt{right}</tex> .
Рассуждения при поиске <tex> \mathtt{answer} </tex>_<tex>\mathtt{right}</tex> аналогичны, только нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 </tex>.
Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex>\mathtt {lcp} </tex> между собой(каждое за <tex> O(1) </tex>), а если дойдет до сравнения символов, то любой символ <tex> p </tex> сравнивается не более одного раза(при сравнении мы берем <tex>\mathtt {max}</tex><tex>(l, r) </tex>, а значит никогда не возвращаемся назад). В самом начале мы посчитали <tex> l </tex> и <tex> r </tex> за <tex> O(p) </tex>. В итоге получаем сложность алгоритма <tex> O(p + log(s)) </tex>. Правда нужен предподсчет, чтобы можно было брать <tex>\mathtt {lcp} </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>, начиная с позиции <tex> r </tex>.
===Рисунки===
Черная вертикальная линия на рисунке обозначает <tex>\mathtt {lcp} </tex> от <tex> i </tex>-го суффикса суффиксного массива <tex> array </tex> и образца <tex> p </tex>. Чем линия длиннее, тем совпадений символов больше.
<tex> L </tex>, <tex> M </tex> и <tex> R </tex> {{---}} то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает <tex> l </tex>, аналогично, самая правая черная вертикальная линия на каждом рисунке означает <tex> r</tex>.
Переменная <tex> m_l </tex> {{---}} это <tex>\mathtt {lcp} </tex> в суффиксном массиве на промежутке <tex> [L, M] </tex>. Переменная <tex> m_r </tex> {{---}} это <tex>\mathtt {lcp} </tex> в суффиксном массиве на промежутке <tex> [M, R] </tex>.
Серым цветом выделен <tex>\mathtt {lcp} </tex> в суффиксном массиве на рассматриваемом промежутке.
===Псевдокод===
Сравнения <tex>< , > , == , \leqslant , \geqslant </tex> при применении к строкам означают полное лексикографическое сравнение строк.
Функция <tex>\mathtt {lcp}</tex>_<tex>\mathtt{common(z(,s, p)}</tex> ищет количество совпадений символов строк <tex>s</tex> и <tex>p</tex> начиная с позиции <tex>z</tex>.
<tex>n</tex> {{---}} длина строки <tex>s</tex>, <tex>w</tex> {{---}} длина строки <tex>p</tex>.
Поиск левой границы ответов <tex> L_p answer </tex>_<tex>left</tex>.
'''function''' find_L_pfind_answer_left(p: '''String''', s: '''String'''):'''int'''
l = '''lcp'''(p, s[array[0]])
r = '''lcp'''(p, s[array[n - 1]])
'''if''' (l == w or p < s[array[0]])
'''else''' '''if''' (p > s[array[n - 1])
'''else'''
L = 0
'''if''' (l <tex>\geqslant</tex> r)
'''if''' (m_l <tex>\geqslant</tex> l)
m = l + '''lcpcommon'''_l(l, s[array[M]], p)
'''else'''
m = m_l
'''else'''
'''if''' (m_r <tex>\geqslant</tex> r)
m = r + '''lcpcommon'''_r(r, s[array[M]], p)
'''else'''
m = m_r
L = M
l = m
== См. также ==
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Структуры данных]]
[[Категория:Суффиксный массив]]
