Изменения

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

Алгоритм Касаи и др.

374 байта добавлено, 21:42, 5 мая 2011
Нет описания правки
<tex>lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) = height[suf^{-1}[i-1]]</tex>, откуда <tex>height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 1</tex>.
}}
 
==Источники==
1. [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%81%D0%B0%D0%B8 Алгоритм Касаи].<br/>
2. [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.8221 T.Kasai, G.Lee, H.Arimura, S.Arikawa, K.Park - Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Application].
Анонимный участник

Навигация