Изменения

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

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

Нет изменений в размере, 18:00, 21 апреля 2012
Нет описания правки
==Некоторые свойства <tex>LCP</tex>==
===Факт №1===
<tex>LCP</tex> между двумя суффиксами {{---}} это минимум <tex>LCP</tex> всех пар соседних суффиксов между ними в суффиксном массиве <tex>Suf</tex>. То есть <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = min_{x < y \le ge z}(LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.
Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.
Анонимный участник

Навигация