Изменения

Перейти к: навигация, поиск

Суффиксный массив

Нет изменений в размере, 18:02, 10 мая 2011
Нет описания правки
== Применения ==
* Позволяет найти все вхождения образца <tex>p</tex> в строку <tex>s</tex> за время <tex>O(|p| + \log(|s|))</tex>
* Массивом <tex>lcp</tex> (longest common prefix) для строки <tex>s</tex> называется массив <tex>lcp[1 .. |s| - 1]</tex>, где <tex>lcp[i]</tex> - длина наибольшего общего префикса суффиксов <tex>suf[i]</tex> и <tex>suf[i - + 1]</tex> строки <tex>s</tex>.<br>Суффиксный массив позволяет построить массив <tex>lcp</tex> для строки <tex>s</tex> за <tex>O(|s|)</tex>.
Анонимный участник

Навигация