Изменения

Рассмотрим такую задачу: у нас есть образец <tex> p </tex>, строка <tex> s </tex>, Далее будут рассмотрены некоторые способы нахождения всех вхождений образца в текст с помощью [[суффиксный массив|суффиксный массивсуффиксного массива]] <tex> array </tex>, построенный для строки <tex> s </tex>. Необходимо найти все вхождения образца <tex> p </tex> в строку <tex> s </tex>.

Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, {{| border="1" |width="20"|# |width="150"|суффикс |width="100"|номер суффикса |- |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 |}суффиксному массиву]] найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца.

Простейший способ узнать=== Псевдокод === '''Поиск диапазона '''  <tex> \mathtt {cmp (k)}</tex> {{---}} функция, сравнивающая строки по <tex>k</tex>-тому символу. <tex> \mathtt {lower}</tex>_<tex>\mathtt {bound (left, right, value, cmp)}</tex>, <tex> \mathtt {upper}</tex>_<tex>\mathtt {bound (left, right, value, cmp)}</tex> {{---}} функции бинарного поиска. Элементы строк нумеруются с единицы '''function''' elementary_search(p: '''String''', s: '''String'''): left = 0 <font color=darkgreen> // left, right {{---}} границы диапазона </font> right = n <font color=darkgreen> // n {{---}} длина образца </font> '''for''' i = 1 '''to''' n left = lower_bound(left, right, p[i], cmp (i) ) right = upper_bound(left, right, p[i], встречается ли образец cmp (i) ) '''if''' (right - left > 0) print left print right '''else''' print "No matches" == Более быстрый поиск == Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex>\mathtt {lcp} </tex> ([[Суффиксный массив#Применения|longest common prefix]]). === Условные обозначения ===  * <tex> \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> и <tex>\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>\mathtt{answer} </tex>_<tex>\mathtt{left}</tex>. Сразу проверим образец с суффиксамипо краям исходного диапазона поиска <tex> L </tex> и <tex> R </tex>: если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить. <tex> \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> ищется при помощи бинарного поиска по суффиксному массиву <tex> array </tex>. На каждом шаге поиска нам надо определять, начинающимися на такую же буквукаком отрезке <tex> [L, M] </tex> или <tex> [M, R] </tex> надо продолжать поиск границы <tex> \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(log|s|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 <br/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> l \geqslant r </tex>: [[Файл:left.png]] Иллюстрации возможных случаев при <tex> l < r </tex>: [[Файл:Right2.png]] ===Псевдокод===Массивы и строки нумеруются с нуля.  Сравнения <tex><_z , >_z , =_z , \leqslant_z , \geqslant_z </tex> означают лексикографическое сравнение двух строк по их первым <tex>z</tex> символам. Сравнения <tex>< , > , == , \leqslant , \geqslant </tex> при применении к строкам означают полное лексикографическое сравнение строк. Функция <tex>\mathtt {common(z,s, p)}</tex> ищет количество совпадений символов строк <tex>s</tex> и <tex>p</tex> начиная с позиции <tex>z</tex>.

{| border="1" |width="80"|образец |width="150"|''<span style="color:#FF00FF"tex>in</spantex>ss'' |width="150"|''<span style="color:#FF00FF">is</span>s'' |width="150"|''<span style="color:#FF00FF">iss</span>'' |{{- | |''<span style="color:#FF00FF">i</span>'' |i |i |- | |''<span style="color:#FF00FF">i</span>ppi'' |ippi |ippi |- | |''<span style="color:#FF00FF">i</span>ssippi'' |''<span style="color:#FF00FF">is</span>sippi'' |''<span style="color:#FF00FF">iss</span>ippi'' |- | |''<span style="color:#FF00FF">i</span>ssissippi'' |''<span style="color:#FF00FF">is</span>sissippi'' |''<span style="color:#FF00FF">iss</span>issippi'' |- | |mississippi |mississippi |mississippi |- | |pi |pi |pi |- | |ppi |ppi |ppi |- | |sippi |sippi |sippi |- | |sissippi |sissippi |sissippi |- | |ssippi |ssippi |ssippi |- | |ssissippi |ssissippi |ssissippi |}В примере показано, какие суффиксы на каждом шаге алгоритма удовлетворяют нашему образцу: на } длина строки <tex> i s</tex>-ом шаге суффикс является подходящим, если <tex> i w</tex> его первых символов совпадают с {{---}} длина строки <tex> i p</tex> первыми символами образца. Каждый шаг к рассмотрению добавляется лишь один новый символ образца. В графе "образец" розовым цветом выделен префикс образца, который ищется на данном шаге, а под образцом располагаются суффиксы строки, префиксы которых выделены розовым цветом, если на данном шаге суффикс подходит. <br>Как видно из примера образцу удовлетворяют суффиксы 3 и 4, начинающиеся на 5 и 2 позициях в строке соответственно(позицию можно посмотреть в таблице повыше).

Поиск диапазона /*p - образец n - длина образца left - левая граница диапазона // изначально равна единице right - правая граница диапазона // изначально равна длине строки lh - вспомогательная переменная для определения левой границы диапазона rg - вспомогательная переменная для определения правой границы диапазона find - функция уточнения диапазона элементы строк и массивов нумеруются с единицы*/ for i = 1 to n { lh = n + 1 rh = 0 find(left, right, i) left = lh right = rh } if (left != 0 && right != n + 1) { ответов <tex> answer <// если диапазон не пуст yield tex>_<tex>left <// вывод левой границы диапазона yield right // вывод правой границы диапазона } else yield "No matches" // вывод информации об отсутствии вхожденийtex>.

Бинарный поиск для уточнения диапазона - функция find '''function''' find_answer_left(p: '''String''', s: '''String'''): '''int''' l= '''lcp'''(p, s[array[0]]) r= '''lcp'''(p, ks[array[n - 1]]) /* '''if''' (l - левая граница диапазона при поиске== w or p < s[array[0]]) r - правая граница диапазона при поиске answer_left = 0 k '''else''' '''if''' (p > s[array[n - номер символа образца, с которым происходит проверка на данном шаге1]) s - строка answer_left = n length - длина строки '''else''' array - суффиксный массив L = 0 x R = n - индекс, стоящий по середине между l и r*/1 if '''while''' (l R - L > r1)'''do''' return x M = (l L + rR) / 2 if m_l = '''lcp'''(array[xL], array[M] + k - 1 <= length){ if m_r = '''lcp'''(s[array[xM] + k - 1] == p, array[kR]){ '''if ''' (x l < lhtex>\geqslant</tex> r) lh = x '''if ''' (x m_l <tex>\geqslant</tex> rhl) rh m = x findl + '''common'''(l, x - 1s[array[M]], kp) find '''else''' m = m_l '''else''' '''if''' (x + 1, m_r <tex>\geqslant</tex> r, k) } else { if m = r + '''common'''(r, s[array[xM] + k - 1] > , p[k]) { find(l, x - 1, k) '''else''' } else { m = m_r '''if ''' (m == w || p <tex>\leqslant</tex><tex>_m</tex> s[array[xM] + k - 1] < p[k]) { find(x + 1, R = M r, k)= m } '''else''' } else { L = M find( l, x - 1, k)= m find(x + 1, r, k) } answer_left = R

=== Более быстрый поиск =См. также ==* [[Алгоритм цифровой сортировки суффиксов циклической строки]]* [[Алгоритм Касаи и др.]]* [[Построение суффиксного массива с помощью стандартных методов сортировки]]

Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex> lcp </tex> (longest common prefix). <br>Пусть <tex> L_p </tex> и <tex> R_p </tex> - левая и правая границы диапазона ответов. В пределах этого диапазона в суффиксном массиве <tex> array </tex> лежат суффиксы, префиксы которых полностью совпадают с образцом <tex> p </tex>. Пусть <tex> L </tex> - левая граница диапазона поиска (изначально равна 0), <tex> R </tex> - правая граница диапазона поиска (изначально равна <tex> |S| - 1 </tex>), а <tex> M = (L + R) / 2 </tex>. <br>Пусть <tex> l = lcp(array[L], p) </tex>, а <tex> r Источники информации== lcp(array* [R], p) <http:/tex>. В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>habrahabr. <br>Пусть <tex> m_l = lcp(array[L], array[M]) <ru/tex>, а <tex> r_l = lcp(array[M],array[R]) </tex>. Подсчет <tex> m_l <blogs/tex> и <tex> m_r <algorithm/tex> можно производить за <tex> O(1) <115346/tex>, если применять [[Алгоритм ФаракаHabrahabr {{---}} Суффиксный массив {{--Колтона и Бендера|Алгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов из диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах (Аналогично для диапазона <tex> [M, R}} удобная замена суффиксного дерева] </tex>). <br>Рассмотрим поиск левой границы диапазона ответов <tex> L_p </tex>(поиск правой границы производится аналогично)*U. <br>Сразу проверим образец с краями исходного диапазона поискаManber and G. Если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе, и поиск можно прекратитьMayers. <br>Границы диапазона ответов ищутся при помощи бинарного поиска. На каждом шаге поиска нам надо определять на каком отрезке (<tex> [L, M] </tex> или <tex> [M, L] </tex>) надо продолжать поиск <tex> L_p </tex>. Сравним <tex> m_l </tex> и <tex> m_r </tex>. Если <tex> m_l > m_r </tex>, то возможно одно из двух{{---}} "Suffix arrays: <br>1) <tex> m_l > l </tex>. Это означает, что каждый суффикс из диапазона <tex> [L, M] </tex> не подходит для <tex> L_p </tex>, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. <tex> l </tex> при этом не меняется, а <tex> L = M </tex>. <br>2) <tex> m_l < l </tex>. Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> M </tex>. Очевидно, что поиск надо продолжать между <tex> L </tex> и <tex> M </tex>, то есть <tex> R = M </tex>, а новое значение <tex> r = m_l </tex>. <br>Если <tex> m_l < m_r </tex>, то действия аналогичны, только сравнения надо проводить с <tex> m_r </tex>, и во втором случае меняется <tex> L </tex> и <tex> l </tex>.Осталось рассмотреть случай, когда <tex> m_l = l </tex> и <tex> m_r = r </tex>. Если хоть одно равенство не выполняется, то результат известен из предыдущего абзаца. Тогда ясно, что <tex> lcp(p, array[M]) </tex> никак не меньше <tex> max(l, r) </tex>. А значит можно сравнивать символы суффикса в позиции <tex> array[M] </tex> и образца начиная с <tex> max(l, r) </tex> позиции.При сравнении мы либо полностью найдем вхождение образца в суффикс, либо на какомA new method for on-то шаге <tex> k </tex> наткнемся на различие . В первом случае нам надо определять дальнейшее место поиска исходя из того, что мы ищем <tex> L_p </tex> или <tex> R_p </tex> (мы искали <tex> L_p </tex>, поэтому <tex> r = max(l, r) + k </tex>, <tex> R = M </tex>). Во втором случае все определяется лексикографически. <br>Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex> lcp </tex> между собой, а если уж и дойдет до сравнения символов, то любой символ <tex> p </tex> сравнивается не более одного раза(мы берем <tex> max(l, r) </tex>, а значит никогда не возвращаемся назад). Получаем сложность алгоритма <tex> O(plog(s)) </tex>. Правда нужен предподсчет, чтобы можно было брать <tex> lcp </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>.line string searches"

==Литература==[[Категория:Алгоритмы и структуры данных]]* http[[Категория://habrahabr.ru/blogs/algorithm/115346/Структуры данных]]*U. Manber and G. Mayers. "Suffix arrays[[Категория: A new method for on-line string searches"Суффиксный массив]]