Алгоритм поиска подстроки в строке с помощью суффиксного массива — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Более быстрый поиск)
м (Источники информации)
(не показана 41 промежуточная версия 2 участников)
Строка 13: Строка 13:
 
'''Поиск диапазона '''  
 
'''Поиск диапазона '''  
  
<tex> \mathtt cmp (k)</tex> {{---}}  функция, сравнивающая строки по k-тому символу.
+
<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> {{---}} функции бинарного поиска.
+
<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():
+
  '''function''' elementary_search(p: '''String''', s: '''String'''):  
     left = 0;                                         <font color=darkgreen> // left, right {{---}} границы диапазона </font>
+
     left = 0                                        <font color=darkgreen> // left, right {{---}} границы диапазона </font>
     right = n;                                       <font color=darkgreen> //  n {{---}}  длина образца </font>
+
     right = n                                        <font color=darkgreen> //  n {{---}}  длина образца </font>
     '''for''' i = 1 '''to''' n {
+
     '''for''' i = 1 '''to''' n  
         left = '''lower_bound'''(left, right, p[i], cmp (i) );
+
         left = lower_bound(left, right, p[i], cmp (i) )
         right = '''upper_bound'''(left, right, p[i], cmp (i) );
+
         right = upper_bound(left, right, p[i], cmp (i) )
    }
+
     '''if''' (right - left > 0)  
     '''if''' (right - left > 0)
+
         print left                   
         yield left;                    
+
         print right                 
         yield right;                  
+
     '''else'''
     } '''else'''
+
         print "No matches"
         yield "No matches";
 
  
 
== Более быстрый поиск ==
 
== Более быстрый поиск ==
  
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex>\mathtt {lcp} </tex> (longest common prefix).
+
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex>\mathtt {lcp} </tex> ([[Суффиксный массив#Применения|longest common prefix]]).
  
=== Условные обозначения ===
+
=== Условные обозначения ===  
'''Алгоритм:'''
 
* <tex> L_p </tex> и <tex> R_p </tex> {{---}} левая и правая границы диапазона ответов в суффиксном массиве <tex> array </tex>.
 
  
У любого суффикса в пределах этого диапазона есть префикс, который полностью совпадает с образцом.
+
* <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>0</tex>).
+
=== Алгоритм ===
* <tex> R </tex> {{---}} правая граница диапазона поиска (изначально равна <tex> |S| - 1 </tex>).
 
* <tex> M = (L + R) / 2 </tex>.
 
  
* <tex> l = </tex><tex>\mathtt {lcp}</tex><tex>(array[L], p) </tex>.
+
Если диапазон ответов не пустой, то у любого суффикса в пределах диапазона ответов есть префикс, который полностью совпадает с образцом.
* <tex> r = </tex><tex>\mathtt {lcp}</tex><tex>(array[R], p) </tex>.  
+
 
+
В самом начале просто посчитаем <tex> l</tex> и <tex> r </tex> за линейное время с помощью [[Алгоритм Касаи и др.|алгоритма Касаи, Арикавы, Аримуры, Ли и Парка]], а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>.
В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>.
 
 
 
* <tex> m_l = </tex><tex>\mathtt {lcp}</tex><tex>(array[L], array[M]) </tex>.
 
* <tex> m_r = </tex><tex>\mathtt {lcp}</tex><tex>(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> совпадений в префиксах.
 
Подсчет <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 {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> L_p </tex>.
+
Рассмотрим поиск левой границы диапазона ответов <tex>\mathtt{answer} </tex>_<tex>\mathtt{left}</tex>.
  
 
Сразу проверим образец с суффиксами по краям исходного диапазона поиска <tex> L </tex> и <tex> R </tex>: если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить.
 
Сразу проверим образец с суффиксами по краям исходного диапазона поиска <tex> L </tex> и <tex> R </tex>: если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить.
  
<tex> L_p </tex> ищется при помощи бинарного поиска по суффиксному массиву <tex> array </tex>. На каждом шаге поиска нам надо определять, на каком отрезке <tex> [L, M] </tex> или <tex> [M, R] </tex> надо продолжать поиск границы <tex> L_p </tex>. Каждую итерацию бинарного поиска будем сравнивать <tex> l </tex> и <tex> r </tex>. Если <tex> l \geqslant r </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> [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> [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> m_l < l </tex>. Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> M </tex>. Очевидно, что поиск надо продолжать между <tex> L </tex> и <tex> M </tex>, то есть <tex> R = M </tex>, а новое значение <tex> r = m_l </tex>.  
 
[[Файл:left.png]]
 
 
 
Если <tex> l < r </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> 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>\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> 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> .
  
[[Файл:Right2.png]]
+
Рассуждения при поиске <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> l \geqslant r </tex>:
  
Бинарный поиск будет работать до тех пор, пока <tex> R - L > 1 </tex>. После этого можно присвоить левой границе диапазона ответов <tex> L_p = R </tex> и переходить к поиску правой границы диапазона ответов <tex> R_p </tex>.
+
[[Файл:left.png]]
  
Рассуждения при поиске <tex> R_p </tex> аналогичны, только нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 </tex>.
+
Иллюстрации возможных случаев при <tex> l < 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]]
  
 
===Псевдокод===
 
===Псевдокод===
Строка 96: Строка 99:
 
Сравнения <tex>< , > , == ,  \leqslant ,  \geqslant </tex> при применении к строкам означают полное лексикографическое сравнение строк.
 
Сравнения <tex>< , > , == ,  \leqslant ,  \geqslant </tex> при применении к строкам означают полное лексикографическое сравнение строк.
  
Функция <tex>\mathtt {lcp_z}</tex><tex>(s, p)</tex> ищет количество совпадений символов строк <tex>s</tex> и <tex>p</tex> начиная с позиции <tex>z</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>n</tex> {{---}} длина строки <tex>s</tex>, <tex>w</tex> {{---}} длина строки <tex>p</tex>.
Строка 103: Строка 106:
 
   
 
   
  
Поиск левой границы ответов <tex> L_p </tex>.
+
Поиск левой границы ответов <tex> answer </tex>_<tex>left</tex>.
  
  '''function''' find_L_p():
+
  '''function''' find_answer_left(p: '''String''', s: '''String'''): '''int'''
     l = '''lcp'''(p, s[array[0]]);
+
     l = '''lcp'''(p, s[array[0]])
     r = '''lcp'''(p, s[array[n - 1]]);
+
     r = '''lcp'''(p, s[array[n - 1]])
 
     '''if''' (l == w or p < s[array[0]])
 
     '''if''' (l == w or p < s[array[0]])
         L_p = 0;
+
         answer_left = 0  
 
     '''else''' '''if''' (p > s[array[n - 1])
 
     '''else''' '''if''' (p > s[array[n - 1])
         L_p = n;
+
         answer_left = n
     '''else''' {
+
     '''else'''  
         L = 0;
+
         L = 0
         R = n - 1;
+
         R = n - 1
         '''while''' (R - L > 1) '''do''' {
+
         '''while''' (R - L > 1) '''do'''  
             M = (L + R) / 2;
+
             M = (L + R) / 2
             m_l = '''lcp'''(array[L], array[M]);
+
             m_l = '''lcp'''(array[L], array[M])
             m_r = '''lcp'''(array[M], array[R]);
+
             m_r = '''lcp'''(array[M], array[R])
 
             '''if''' (l <tex>\geqslant</tex> r)
 
             '''if''' (l <tex>\geqslant</tex> r)
 
                 '''if''' (m_l <tex>\geqslant</tex> l)
 
                 '''if''' (m_l <tex>\geqslant</tex> l)
                     m = l + '''lcp'''_l(s[array[M]], p);
+
                     m = l + '''common'''(l, s[array[M]], p)
 
                 '''else'''
 
                 '''else'''
                     m = m_l;
+
                     m = m_l
 
             '''else'''
 
             '''else'''
 
                 '''if''' (m_r <tex>\geqslant</tex> r)
 
                 '''if''' (m_r <tex>\geqslant</tex> r)
                     m = r + '''lcp'''_r(s[array[M]], p);
+
                     m = r + '''common'''(r, s[array[M]], p)
 
                 '''else'''
 
                 '''else'''
                     m = m_r;
+
                     m = m_r
 
             '''if''' (m == w || p <tex>\leqslant</tex><tex>_m</tex> s[array[M]]){
 
             '''if''' (m == w || p <tex>\leqslant</tex><tex>_m</tex> s[array[M]]){
                 R = M;
+
                 R = M
                 r = m;
+
                 r = m
             } '''else''' {
+
             '''else'''  
                 L = M;
+
                 L = M
                 l = m;
+
                 l = m
            }
+
         answer_left = R
         }
 
        L_p = R;
 
    }
 
  
 
== См. также ==
 
== См. также ==
Строка 150: Строка 150:
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Структуры данных]]
 
[[Категория:Суффиксный массив]]
 
[[Категория:Суффиксный массив]]

Версия 21:39, 1 апреля 2016

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

Наивный алгоритм поиска

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

Бинарный поиск работает за время равное [math] O(\log|s|) [/math], а сравнение суффикса с образцом не может превышать длины образца.

Таким образом время работы алгоритмы [math] O(|p|\log|s|)[/math], где [math] s [/math] — текст, [math] p [/math] — образец.

Псевдокод

Поиск диапазона

[math] \mathtt {cmp (k)}[/math] — функция, сравнивающая строки по [math]k[/math]-тому символу.

[math] \mathtt {lower}[/math]_[math]\mathtt {bound (left, right, value, cmp)}[/math], [math] \mathtt {upper}[/math]_[math]\mathtt {bound (left, right, value, cmp)}[/math] — функции бинарного поиска.

Элементы строк нумеруются с единицы

function elementary_search(p: String, s: String): 
    left = 0                                          // left, right — границы диапазона 
    right = n                                         //  n —  длина образца 
    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"

Более быстрый поиск

Существует более быстрый алгоритм поиска образца в строке. Для этого используется [math]\mathtt {lcp} [/math] (longest common prefix).

Условные обозначения

  • [math] \mathtt{answer} [/math]_[math]\mathtt{left}[/math] и [math]\mathtt{answer} [/math]_[math]\mathtt{right}[/math] — левая и правая границы диапазона ответов в суффиксном массиве [math] array [/math],
  • [math] L [/math] — левая граница текущего диапазона поиска (изначально равна [math]0[/math]),
  • [math] R [/math] — правая граница текущего диапазона поиска (изначально равна [math] |S| - 1 [/math]),
  • [math] M = (L + R) / 2 [/math] — середина текущего диапазона поиска,
  • [math] l = [/math] [math]\mathtt {lcp(array[L], p)} [/math] — длина общего префикса образца и левого края текущего диапазона поиска,
  • [math] r = [/math] [math]\mathtt {lcp(array[R], p)} [/math] — длина общего префикса образца и правого края текущего диапазона поиска,
  • [math] m_l = [/math] [math]\mathtt {lcp(array[L], array[M])} [/math] — длина общего префикса середины текущего диапазона и левого края текущего диапазона поиска,
  • [math] m_r = [/math] [math]\mathtt {lcp(array[M], array[R])} [/math] — длина общего префикса середины текущего диапазона и правого края текущего диапазона поиска.

Алгоритм

Если диапазон ответов не пустой, то у любого суффикса в пределах диапазона ответов есть префикс, который полностью совпадает с образцом.

В самом начале просто посчитаем [math] l[/math] и [math] r [/math] за линейное время с помощью алгоритма Касаи, Арикавы, Аримуры, Ли и Парка, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за [math] O(1) [/math].

Подсчет [math] m_l [/math] и [math] m_r [/math] можно производить за [math] O(1) [/math], если применять алгоритм Фарака-Колтона и Бендера. Любая пара суффиксов [math] array [/math] из диапазона [math] [L, M] [/math] имеет хотя бы [math] m_l [/math] совпадений в префиксах. Аналогично любая пара суффиксов [math] array [/math] из диапазона [math] [M, R] [/math] имеет хотя бы [math] m_r [/math] совпадений в префиксах.

Поиск границ диапазона ответов

Рассмотрим поиск левой границы диапазона ответов [math]\mathtt{answer} [/math]_[math]\mathtt{left}[/math].

Сразу проверим образец с суффиксами по краям исходного диапазона поиска [math] L [/math] и [math] R [/math]: если образец лексикографически больше последнего суффикса [math] array [/math] или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить.

[math] \mathtt{answer} [/math]_[math]\mathtt{left}[/math] ищется при помощи бинарного поиска по суффиксному массиву [math] array [/math]. На каждом шаге поиска нам надо определять, на каком отрезке [math] [L, M] [/math] или [math] [M, R] [/math] надо продолжать поиск границы [math] \mathtt{answer} [/math]_[math]\mathtt{left}[/math] . Каждую итерацию бинарного поиска будем сравнивать [math] l [/math] и [math] r [/math]. Если [math] l \geqslant r [/math], то возможно одно из трех:

  1. [math] m_l \gt l [/math]. Это означает, что каждая пара суффиксов из диапазона [math] [L, M] [/math] имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне [math] [M, R] [/math]. Значение [math] l [/math] при этом не меняется, а [math] L = M [/math].
  2. [math] m_l = l [/math]. Это означает, что у каждого суффикса из [math] [L, M] [/math] есть хотя бы [math] l [/math] совпадений с образцом. Проверим суффикс в позиции [math] M [/math], так как с ним совпадений у образца может получиться больше. Начнем сравнивать суффикс в позиции [math] M [/math] начиная с [math] l [/math]-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге [math] k [/math] получим несоответствие. В первом случае [math] R = M [/math] и [math] r = |p| [/math], так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ [math] l + k + 1 [/math] у образца меньше, чем у суффикса, то [math] R = M [/math] и [math] r = l + k + 1[/math], иначе [math] L = M [/math] и [math] l = l + k + 1[/math].
  3. [math] m_l \lt l [/math]. Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции [math] M [/math]. Очевидно, что поиск надо продолжать между [math] L [/math] и [math] M [/math], то есть [math] R = M [/math], а новое значение [math] r = m_l [/math].

Если [math] l \lt r [/math], то действия аналогичны. Также три случая:

  1. [math] m_r \gt r [/math]. Сдвигаем [math] R [/math] в [math] M [/math]. Значение [math] r [/math] не изменяется.
  2. [math] m_r = r [/math]. Считаем [math]\mathtt {lcp} [/math] для образца и суффикса, стоящего в позиции [math] M [/math], начиная с позиции [math] r [/math].
  3. [math] m_r \lt r [/math]. Сдвигаем [math] L [/math] в [math] M [/math], [math] l = m_r [/math].

Бинарный поиск будет работать до тех пор, пока [math] R - L \gt 1 [/math]. После этого можно присвоить левой границе диапазона ответов [math] \mathtt{answer} [/math]_[math]\mathtt{left} = R [/math] и переходить к поиску правой границы диапазона ответов [math] \mathtt{answer} [/math]_[math]\mathtt{right}[/math] .

Рассуждения при поиске [math] \mathtt{answer} [/math]_[math]\mathtt{right}[/math] аналогичны, только нужно не забыть изменить границы поиска на изначальные [math] L = 0 [/math] и [math] R = |s| - 1 [/math].

Таким образом часть бинарного поиска мы сделаем при сравнении нескольких [math]\mathtt {lcp} [/math] между собой(каждое за [math] O(1) [/math]), а если дойдет до сравнения символов, то любой символ [math] p [/math] сравнивается не более одного раза(при сравнении мы берем [math]\mathtt {max}[/math][math](l, r) [/math], а значит никогда не возвращаемся назад). В самом начале мы посчитали [math] l [/math] и [math] r [/math] за [math] O(p) [/math]. В итоге получаем сложность алгоритма [math] O(p + log(s)) [/math]. Правда нужен предподсчет, чтобы можно было брать [math]\mathtt {lcp} [/math] для двух любых суффиксов [math] array [/math] за [math] O(1) [/math], начиная с позиции [math] r [/math].

Рисунки

Черная вертикальная линия на рисунке обозначает [math]\mathtt {lcp} [/math] от [math] i [/math]-го суффикса суффиксного массива [math] array [/math] и образца [math] p [/math]. Чем линия длиннее, тем совпадений символов больше.

[math] L [/math], [math] M [/math] и [math] R [/math] — то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает [math] l [/math], аналогично, самая правая черная вертикальная линия на каждом рисунке означает [math] r[/math].

Переменная [math] m_l [/math] — это [math]\mathtt {lcp} [/math] в суффиксном массиве на промежутке [math] [L, M] [/math]. Переменная [math] m_r [/math] — это [math]\mathtt {lcp} [/math] в суффиксном массиве на промежутке [math] [M, R] [/math]. Серым цветом выделен [math]\mathtt {lcp} [/math] в суффиксном массиве на рассматриваемом промежутке.

Иллюстраци возможных случаев при [math] l \geqslant r [/math]:

Left.png

Иллюстрации возможных случаев при [math] l \lt r [/math]:

Right2.png

Псевдокод

Массивы и строки нумеруются с нуля.

Сравнения [math]\lt _z , \gt _z , =_z , \leqslant_z , \geqslant_z [/math] означают лексикографическое сравнение двух строк по их первым [math]z[/math] символам.

Сравнения [math]\lt , \gt , == , \leqslant , \geqslant [/math] при применении к строкам означают полное лексикографическое сравнение строк.

Функция [math]\mathtt {common(z,s, p)}[/math] ищет количество совпадений символов строк [math]s[/math] и [math]p[/math] начиная с позиции [math]z[/math].

[math]n[/math] — длина строки [math]s[/math], [math]w[/math] — длина строки [math]p[/math].

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


Поиск левой границы ответов [math] answer [/math]_[math]left[/math].

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 [math]\geqslant[/math] r)
                if (m_l [math]\geqslant[/math] l)
                    m = l + common(l, s[array[M]], p)
                else
                    m = m_l
            else
                if (m_r [math]\geqslant[/math] r)
                    m = r + common(r, s[array[M]], p)
                else
                    m = m_r
            if (m == w || p [math]\leqslant[/math][math]_m[/math] s[array[M]]){
                R = M
                r = m
            else 
                L = M
                l = m
        answer_left = R

См. также

Источники информации