Изменения

Перейти к: навигация, поиск
Более быстрый поиск
Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <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>.
tex>, начиная с позиции <tex> r </tex>.
* с) <tex> r > m_r </tex>. Сдвигаем <tex> L </tex> в <tex> M </tex>, <tex> l = m_r </tex>.
===Псевдокод===
13
правок

Навигация