Изменения

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

289 байт убрано, 15:54, 8 июня 2014

→‎Шаг 1: суффиксное дерево для сжатой строки

* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом:

[[Файл:tree101232.png|300px|thumb|right|суффиксное дерево для сжатой строки]]

~~{|class="wikitable"~~

|+

~~!width="20%"|ID !!width="20%"|LCP !!width="20%"|STR~~

~~|- align = "center"~~

|1

|0

~~|0 1 2 3 2~~

~~|- align = "center"~~

|0

~~|1 0 1 2 3 2~~

~~|- align = "center"~~

|2

|1

~~|1 2 3 2~~

~~|- align = "center"~~

|3

|0

~~|2 3 2~~

~~|- align = "center"~~

|5

|1

|2

~~|- align = "center"~~

|4

|0

~~|3 2~~

|}

=== Шаг 2: построение чётного дерева ===

497

правок