Алгоритм Фараха

Материал из Викиконспекты
Версия от 12:33, 13 мая 2014; Slavian (обсуждение | вклад) (init)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Алгоритм Фарача — алгоритм построения суффиксного дерева для заданной строки [math]s[/math], который выполняется за время [math]O(N)[/math], при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите [math]\sigma = {1, 2.... , а}[/math], при этом накладывается дополнительное условие, что [math]a \in O(N)[/math]. Такие алфавиты часто встречаются на практике.


Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку.