Построение суффиксного дерева в иерархической памяти: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
(2) Задать начальное значение <math>\mathcal{T}_S \;</math> в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс <math>\mathcal{A}_S \;</math> [1]. | (2) Задать начальное значение <math>\mathcal{T}_S \;</math> в виде единственного ребра, соединяющего корень с листом, ссылающимся на суффикс <math>\mathcal{A}_S \;</math> [1]. | ||
(2) For i = 2, ..., n: | (2) For i = 2, ..., n: | ||
(2.1) Создать новый лист <math>\ell_i \;</math>, ссылающийся на суффикс <math>\mathcal{ | (2.1) Создать новый лист <math>\ell_i \;</math>, ссылающийся на суффикс <math>\mathcal{A}_S [i] \;</math>. | ||
(2.2) Двигаться вверх от <math>\ell_{i - 1} \;</math> до тех пор, пока не встретится вершина <math>u_i \;</math> с длиной строки <math>x_i \le lcp_S[i] \;</math>. | (2.2) Двигаться вверх от <math>\ell_{i - 1} \;</math> до тех пор, пока не встретится вершина <math>u_i \;</math> с длиной строки <math>x_i \le lcp_S[i] \;</math>. | ||
(2.3) Если <math>x_i = lcp_S[i] \;</math>, присоединить лист <math>\ell_i \;</math> к <math>u_i \;</math>. | (2.3) Если <math>x_i = lcp_S[i] \;</math>, присоединить лист <math>\ell_i \;</math> к <math>u_i \;</math>. | ||