Изменения

{{В разработке}} Здесь мы рассмотрим Далее будут рассмотрены некоторые способы нахождения всех вхождений образца в текст с помощью [[суффиксный массив|суффиксного массива]].

Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это {{---}} взять первый символ образца и [[Целочисленный двоичный поиск|бинарным поиском ]] по [[суффиксный массив|суффиксному массиву]] найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца.  

Таким образом время работы алгоритмы <tex> O(|p|\log|s|)</tex>. , где <tex> s </tex> {{---}} текст, <tex> p <br/tex>{{---}} образец.

 <tex> \mathtt {cmp (k)}</tex> {{---}} функция, сравнивающая строки по <tex>k</* p tex>- образецтому символу. n - длина образца <tex> \mathtt {lower}</tex>_<tex>\mathtt {bound (left - левая граница диапазона , right, value, cmp)}</tex>, <tex> \mathtt {upper}</ изначально равна единице tex>_<tex>\mathtt {bound (left, right , value, cmp)}</tex> {{- правая граница диапазона // изначально равна длине строки lh - вспомогательная переменная для определения левой границы диапазона rg - вспомогательная переменная для определения правой границы диапазона}} функции бинарного поиска. find - функция уточнения диапазона элементы Элементы строк и массивов нумеруются с единицы */

'''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 { lh = n + 1 rh left = 0 findlower_bound(left, right, p[i], cmp (i) ) right = upper_bound(left = lh , right = rh, p[i], cmp (i) ) } '''if ''' (right - left != > 0 && right != n + 1) { yield print left yield print right } '''else''' yield print "No matches"

'''Бинарный == Более быстрый поиск для уточнения диапазона''' - функция find== Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex>\mathtt {lcp} </tex> (l, r, k[[Суффиксный массив#Применения|longest common prefix]]). === Условные обозначения ===   * <tex> \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> и <tex>\mathtt{answer} </tex>_<tex>\mathtt{right}</tex> {{---}} левая и правая границы диапазона ответов в суффиксном массиве <tex> array </tex>,* l <tex> L </tex> {{--- }} левая граница текущего диапазона при поискепоиска (изначально равна <tex>0</tex>), r * <tex> R </tex> {{--- }} правая граница текущего диапазона при поискепоиска (изначально равна <tex> |S| - 1 </tex>), k * <tex> M = (L + R) / 2 </tex> {{---}} середина текущего диапазона поиска,* <tex> l = </tex> <tex>\mathtt {lcp(array[L], p)} </tex> {{--- номер символа }} длина общего префикса образцаи левого края текущего диапазона поиска, с которым происходит проверка на данном шаге s * <tex> r = </tex> <tex>\mathtt {lcp(array[R], p)} </tex> {{-- строка length - }} длина строкиобщего префикса образца и правого края текущего диапазона поиска, * <tex> m_l = </tex> <tex>\mathtt {lcp(array[L], array [M])} </tex> {{-- суффиксный массив x - индекс}} длина общего префикса середины текущего диапазона и левого края текущего диапазона поиска, стоящий по середине между l и r *<tex> m_r = </tex> <tex>\mathtt {lcp(array[M], array[R])} </tex> {{---}} длина общего префикса середины текущего диапазона и правого края текущего диапазона поиска. === Алгоритм === Если диапазон ответов не пустой, то у любого суффикса в пределах диапазона ответов есть префикс, который полностью совпадает с образцом.

if (В самом начале просто посчитаем <tex> l </tex> и <tex> r) return x = (l + r) </ 2 if (array[x] + k - 1 <= length){ if (stex> за линейное время с помощью [array[x] + k - 1] == p[k]){ if (x < lh) lh = x if (x > rh) rh = x find(l, x - 1Алгоритм Касаи и др.|алгоритма Касаи, k) find(x + 1Арикавы, rАримуры, k) } else { if (s[array[xЛи и Парка] + k - 1] > p[k]) { find(l, x - 1а во время выполнения алгоритма прямой пересчет производиться не будет, k) } else { if (s[array[x] + k - 1] изменения будут происходить за < p[k]) { findtex> O(x + 1, r, k) } } else { find(l, x - 1, k) find(x + 1, r, k) }</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> lcp </tex> (longest common prefix). <br>Пусть <tex> L_p </tex> и <tex> R_p </tex> - левая и правая границы диапазона ответов в суффиксном массиве <tex> array </tex>. У любого суффикса в пределах этого диапазона есть префикс, который полностью совпадает с образцом. <br>Пусть <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) </tex>. В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>. <br>Пусть <tex> m_l = lcp(array[L], array[M]) </tex>, а <tex> m_r = lcp(array[M],array[R]) </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> совпадений в префиксах. <br>Рассмотрим поиск левой границы диапазона ответов <tex> L_p </tex>. <br>Сразу проверим образец с суффиксами по краям исходного диапазона поиска <tex> L </tex> и <tex> R </tex>: если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить. <br><tex> L_p </tex> ищется Рассуждения при помощи бинарного поиска по суффиксному массиву поиске <tex> array \mathtt{answer} </tex>. На каждом шаге поиска нам надо определять, на каком отрезке _<tex> [L, M] </tex> или <tex> [M, R] </tex> надо продолжать поиск границы <tex> L_p </tex>. Каждую итерацию бинарного поиска будем сравнивать <tex> l </tex> и <tex> r </tex>. Если <tex> l \ge r </tex>, то возможно одно из трех: <br>* 1. <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 </tex> у образца меньше, чем у суффикса, то <tex> R = M </tex> и <tex> r = l + k </tex>, иначе <tex> L = M </tex> и <tex> l = l + k </tex>.<br>* 2. <tex> m_l > l </tex>. Это означает, что каждая пара суффиксов из диапазона <tex> [L, M] </tex> имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. Значение <tex> l </tex> при этом не меняется, а <tex> L = M </tex>. <br>* 3. <tex> m_l < l </tex>. Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> M mathtt{right}</tex>. Очевидно, что поиск надо продолжать между <tex> L </tex> и <tex> M </tex>, то есть <tex> R = M </tex>, а новое значение <tex> r = m_l </tex>. <br>Если <tex> l < r </tex>, то действия аналогичны: <br>* 1. <tex> m_r = r </tex>. Это означает, что у каждого суффикса из <tex> [M, R] </tex> есть хотя бы <tex> r </tex> совпадений с образцом. Проверим суффикс в позиции <tex> M </tex>, так как с ним совпадений у образца может получиться больше. Начнем сравнивать суффикс в позиции <tex> M </tex> начиная с <tex> r </tex>-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге <tex> k </tex> получим несоответствие. В первом случае <tex> R = M </tex> и <tex> r = |p| </tex>, так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ <tex> r + k </tex> у образца меньше, чем у суффикса, то <tex> R = M </tex> и <tex> r = r + k </tex>, иначе <tex> L = M </tex> и <tex> l = r + k </tex>. <br>* 2. <tex> m_r > r </tex>. Это означает, что каждая пара суффиксов из диапазона <tex> [M, R] </tex> имеет между собой больше совпадений, чем суффикс с правого края с образцом, поэтому продолжим поиск в диапазоне <tex> [L, M] </tex>. Значение <tex> r </tex> при этом не меняется, а <tex> R = M </tex>. <br>* 3. <tex> m_r < r </tex>. Это означает, что совпадений у суффикса с правого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> M </tex>. Очевидно, что поиск надо продолжать между <tex> M </tex> и <tex> R </tex>, то есть <tex> L = M </tex>, а новое значение <tex> l = m_r </tex>. <br> Бинарный поиск будет работать до тех пор, пока <tex> R - L > 1 </tex>. После этого можно присвоить левой границе диапазона ответов <tex> L_p = R </tex> и переходить к поиску правой границы диапазона ответов <tex> R_p </tex>. <br>Рассуждения при поиске <tex> R_p </tex> аналогичны, только нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 </tex>. <br>Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex> lcp </tex> между собой(каждое за <tex> O(1) </tex>), а если дойдет до сравнения символов, то любой символ <tex> p </tex> сравнивается не более одного раза(при сравнении мы берем <tex> max(l, r) </tex>, а значит никогда не возвращаемся назад). В самом начале мы посчитали <tex> l </tex> и <tex> r </tex> за <tex> O(p) </tex>. В итоге получаем сложность алгоритма <tex> O(p + log(s)) </tex>. Правда нужен предподсчет, чтобы можно было брать <tex> lcp </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>.

Условные обозначения:* 1. Черная вертикальная линия на рисунке обозначает <tex> \mathtt {lcp } </tex> от <tex> i </tex>-го суффикса суффиксного массива <tex> array </tex> и образца <tex> p </tex>. Чем линия длиннее, тем совпадений символов больше. * 2. L, M и R - то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает <tex> l </tex>, аналогично, самая правая черная вертикальная линия на каждом рисунке означает <tex> r </tex>. Переменная <tex> m_l </tex> - это <tex> lcp </tex> в суффиксном массиве на промежутке <tex> [L, M] </tex>. Переменная <tex> m_r </tex> - это <tex> lcp </tex> в суффиксном массиве на промежутке <tex> [M, R] </tex>.* 3. Серым цветом выделен <tex> lcp </tex> в суффиксном массиве на рассматриваемом промежутке.

Простой пример для образца <tex>aaaL </tex> на отсортированных суффиксах строки , <tex> M </tex> и <tex>aaaaaaR </tex>.Жирным выделены буквы, которые на рисунках будут представлены черными линиями (совпадения с образцом), а серым {{---}} совпадения суффиксов друг с другом то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на промежутке каждом рисунке означает <tex> [Ml </tex>, аналогично, R] самая правая черная вертикальная линия на каждом рисунке означает <tex> r</tex>.

Переменная <tex> m_l </tex> {{---}} это <tex>\mathtt {lcp} </tex> в суффиксном массиве на промежутке <tex> [L, M] </tex>. Переменная <tex> m_r </tex> {{---}} это <tex>\mathtt {lcp} </tex> в суффиксном массиве на промежутке <tex> [Файл:examp3M, R] </tex>.Серым цветом выделен <tex>\mathtt {lcp} </tex> в суффиксном массиве на рассматриваемом промежутке.png]]

Дальнейший разбор Иллюстраци возможных случаев никак не связан со строкой <tex>aaaaaa</tex> и образцом <tex>aaa</tex>. <br>Ищется левая граница ответов <tex> L_p </tex>. <br>Разберем случай при <tex> l \ge geqslant r </tex>. Возможны три варианта:

* a) Иллюстрации возможных случаев при <tex> l < m_l r </tex>: [[Файл:Right2.png]] ===Псевдокод===Массивы и строки нумеруются с нуля. Сдвигаем  Сравнения <tex> L </tex_z , > в <tex> M _z , =_z , \leqslant_z , \geqslant_z </tex>. Значение означают лексикографическое сравнение двух строк по их первым <tex> l z</tex> не изменяетсясимволам.* b) Сравнения <tex> l = m_l </tex, >. Считаем <tex> lcp </tex> для образца и суффикса, стоящего в позиции <tex> M </tex>== , \leqslant , начиная с позиции <tex> l \geqslant </tex>при применении к строкам означают полное лексикографическое сравнение строк.* с) Функция <tex> l > m_l \mathtt {common(z,s, p)}</tex>. Сдвигаем ищет количество совпадений символов строк <tex> R s</tex> в и <tex> M p</tex>, начиная с позиции <tex> r = m_l z</tex>.

Разберем случай при <tex> l n< r /tex> {{---}} длина строки <tex>s</tex>, <tex>w</tex> {{---}} длина строки <tex>p</tex>. Также возможны три варианта:

[[Файл:right2В алгоритме используются переменные, введенные выше в разделе "более быстрый поиск".png]]

* a) Поиск левой границы ответов <tex> r < m_r </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>. Значение <tex> r </tex> не изменяется.* b) <tex> r = m_r </tex>. Считаем <tex> lcp </tex> для образца и суффикса, стоящего в позиции <tex> M </tex>, начиная с позиции <tex> r </tex>. * с) <tex> r > m_r </tex>. Сдвигаем <tex> L </tex> в <tex> M answer </tex>, _<tex> l = m_r left</tex>.

'''function''' find_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]]) answer_left =0 '''else''' '''if''' (p > s[array[n - 1]) answer_left =n '''else''' L = 0 R = n - 1 '''while''' (R - L > 1) '''do''' M = (L + R) / 2 m_l = '''lcp'''(array[L], array[M]) m_r = '''lcp'''(array[M], array[R]) '''if''' (l <tex>\geqslant</tex> r) '''if''' (m_l <tex>\geqslant</tex> l) m = l + '''common'''(l, s[array[M]], p) '''else''' m = m_l '''else''' '''if''' (m_r <tex>\geqslant</tex> r) m = r + '''common'''(r, s[array[M]], p) '''else''' m = m_r '''if''' (m == w || p <tex>\leqslant</tex><tex>_m</tex> s[array[M]]){ R = M r = m '''else''' L = M l = m answer_left = R

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

/* Массивы и строки нумеруются с нуля. Сравнения <<math>_z </math> , ><math>_z </math> , =<math>_z </math> , <=<math>_z </math> , >Источники информации=<math>_z </math> означают лексикографическое сравнение двух строк по их первым z символам. Сравнения < , > , == , <= , >= при применении к строкам означают полное лексикографическое сравнение строк* [http://habrahabr. Функция lcp<math>_z<ru/math>(s, p) ищет количество совпадений символов строк s и p начиная с позиции z. n - длина строки s. w - длина строки p. В алгоритме используются переменные, введенные выше в разделе "более быстрый поиск". *blogs/ l = lcp(p, s[array[0]]) r = lcp(p, s[array[n-1]]) if (l == w or p < s[array[0]]) L<math>_p<algorithm/math> = 0 else if (p > s[array[n-1]) L<math>_p<115346/math> = n else Habrahabr {{ L = 0 R = n - 1 while (R - L > 1) do -}} Суффиксный массив { M = (L + R)/2 m<math>_l</math> = lcp(array[L{---}} удобная замена суффиксного дерева],array[M]) m<math>_r</math> = lcp(array[M],array[R]) if (l >= r) if (m<math>_l</math> >= l) m = l + lcp<math>_l</math>(s[array[M]], p) else m = m<math>_l</math> else if (m<math>_r</math> >= r) m = r + lcp<math>_r</math>(s[array[M]], p) else m = m<math>_r</math> if (m == w || p <=<math>_m</math> s[array[M]])*U. Manber and G. Mayers. { R = M r = m } else { L = M l = m ---} } L<math>_p</math> = R }"Suffix arrays: A new method for on-line string searches"

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