LCP массив - LCP array

LCP массив
Тип	Множество
Изобретенный	Манбер и Майерс (1990)
Сложность времени и космическая сложность; в нотация большой O

В Информатика, то самый длинный общий префиксный массив (LCP множество) является вспомогательным структура данных к массив суффиксов. Он хранит длины самых длинных общих префиксов (LCP) между всеми парами последовательных суффиксов в отсортированном массиве суффиксов.

Например, если А := [ааб, ab, abaab, б, бааб] - массив суффиксов, самый длинный общий префикс между А[1] = ааб и А[2] = ab является а который имеет длину 1, поэтому ЧАС[2] = 1 в массиве LCP ЧАС. Аналогичным образом, LCP А[2] = ab и А[3] = abaab является ab, так ЧАС[3] = 2.

Дополнение массива суффиксов массивом LCP позволяет эффективно моделировать нисходящий и восходящий обходы из суффиксное дерево,^[1]^[2] ускоряет сопоставление с образцом в массиве суффиксов^[3] и является предпосылкой для сжатых деревьев суффиксов.^[4]

История

Массив LCP был представлен в 1993 г. Уди Манбер и Джин Майерс рядом с массивом суффиксов, чтобы улучшить время работы алгоритма поиска строки.^[3]

Определение

Позволять ${ displaystyle A}$ быть массив суффиксов строки ${ Displaystyle S = s_ {1}, s_ {2}, ldots s_ {n-1} $}$ длины ${ displaystyle n}$ , куда ${ Displaystyle $}$ это уникальное дозорное письмо, лексикографически меньше, чем любой другой персонаж. Позволять ${ Displaystyle S [я, j]}$ обозначают подстроку ${ displaystyle S}$ начиная с ${ displaystyle i}$ к ${ displaystyle j}$ . Таким образом, ${ Displaystyle S [А [я], п]}$ это ${ displaystyle i}$ th наименьший суффикс ${ displaystyle S}$ .

Позволять ${ displaystyle operatorname {lcp} (v, w)}$ обозначают длину самого длинного общего префикса между двумя строками ${ displaystyle v}$ и ${ displaystyle w}$ . Тогда массив LCP ${ displaystyle H [1, n]}$ представляет собой целочисленный массив размера ${ displaystyle n}$ такой, что ${ displaystyle H [1]}$ не определено и ${ Displaystyle Н [я] = OperatorName {lcp} (S [A [i-1], n], S [A [i], n])}$ для каждого ${ Displaystyle 1 <я Leq п}$ . Таким образом ${ Displaystyle Н [я]}$ хранит длину самого длинного общего префикса лексикографически ${ displaystyle i}$ -й наименьший суффикс и его предшественник в массиве суффиксов.

Разница между массивом LCP и массивом суффиксов:

Массив суффиксов: представляет лексикографический ранг каждого суффикса массива.
Массив LCP: содержит совпадение префикса максимальной длины между двумя последовательными суффиксами после их лексикографической сортировки.

Пример

Рассмотрим строку ${ Displaystyle S = банан $}$ :

я	1	2	3	4	5	6	7
S [i]	б	а	п	а	п	а	$

и соответствующий ему отсортированный массив суффиксов ${ displaystyle A}$ :

я	1	2	3	4	5	6	7
A [i]	7	6	4	2	1	5	3

Массив суффиксов с суффиксами, написанными под ним по вертикали:

я	1	2	3	4	5	6	7
A [i]	7	6	4	2	1	5	3
S [A [i], n] [1]	$	а	а	а	б	п	п
S [A [i], n] [2]		$	п	п	а	а	а
S [A [i], n] [3]			а	а	п	$	п
S [A [i], n] [4]			$	п	а		а
S [A [i], n] [5]				а	п		$
S [A [i], n] [6]				$	а
S [A [i], n] [7]					$

Тогда массив LCP ${ displaystyle H}$ строится путем сравнения лексикографически последовательных суффиксов для определения их самого длинного общего префикса:

я	1	2	3	4	5	6	7
Здравствуй]	неопределенный	0	1	3	0	0	2

Так, например, ${ displaystyle H [3] = 3}$ это длина самого длинного общего префикса ${ displaystyle ana}$ разделяются суффиксами ${ Displaystyle А [3] = S [4,7] = ана $}$ и ${ Displaystyle А [4] = S [2,7] = анана $}$ . Обратите внимание, что ${ displaystyle H [1]}$ не определено, так как нет лексикографически меньшего суффикса.

Эффективные алгоритмы строительства

Алгоритмы построения массива LCP можно разделить на две разные категории: алгоритмы, которые вычисляют массив LCP как побочный продукт для массива суффиксов, и алгоритмы, которые используют уже построенный массив суффиксов для вычисления значений LCP.

Манбер и Майерс (1993) предоставить алгоритм для вычисления массива LCP вместе с массивом суффиксов в ${ Displaystyle О (п журнал п)}$ время. Кярккяйнен и Сандерс (2003) показать, что также можно изменить их ${ Displaystyle О (п)}$ алгоритм времени, так что он также вычисляет массив LCP. Kasai et al. (2001) представить первый ${ Displaystyle О (п)}$ временной алгоритм (FLAAP), который вычисляет массив LCP по тексту и массиву суффиксов.

Предполагая, что каждый текстовый символ занимает один байт, а каждая запись суффикса или массива LCP занимает 4 байта, основным недостатком их алгоритма является занимаемое пространство ${ displaystyle 13n}$ байтов, в то время как исходный вывод (текст, массив суффиксов, массив LCP) занимает только ${ displaystyle 9n}$ байты. Следовательно, Манзини (2004) создали доработанный вариант алгоритма Kasai et al. (2001) (lcp9) и уменьшил занимаемую площадь до ${ displaystyle 9n}$ байты. Кярккяйнен, Манзини и Пуглиси (2009) предоставить еще одно уточнение алгоритма Касаи ( ${ displaystyle Phi}$ -алгоритм), что улучшает время работы. Вместо реального массива LCP, этот алгоритм строит переставлен LCP (PLCP) массив, в котором значения отображаются в текстовом, а не в лексикографическом порядке.

Гог и Охлебуш (2011) предоставляют два алгоритма, которые, хотя и являются теоретически медленными ( ${ Displaystyle О (п ^ {2})}$ ) на практике оказались быстрее, чем упомянутые выше алгоритмы.

По состоянию на 2012 год^{[Обновить]}, самый быстрый в настоящее время алгоритм построения массива LCP с линейным временем связан с Фишер (2011), который, в свою очередь, основан на одном из самых быстрых алгоритмов построения массива суффиксов (SA-IS) Нонг, Чжан и Чан (2009). Фишер и Курпиц (2017) на основе DivSufSort Юты Мори даже быстрее.

Приложения

Как отмечает Абуэльода, Курц и Охлебуш (2004) несколько проблем обработки строк можно решить с помощью следующих видов обходы деревьев:

обход полного дерева суффиксов снизу вверх
обход поддерева суффиксного дерева сверху вниз
обход суффиксного дерева с использованием суффиксных ссылок.

Kasai et al. (2001) показать, как смоделировать обход снизу вверх суффиксное дерево используя только массив суффиксов и массив LCP. Абуэльода, Курц и Охлебуш (2004) дополните массив суффиксов массивом LCP и дополнительными структурами данных и опишите, как это расширенный массив суффиксов можно использовать для моделирования все три вида обходов суффиксного дерева. Фишер и Хойн (2007) уменьшить требования к пространству для расширенного массива суффиксов путем предварительной обработки массива LCP для минимальный диапазон запросов. Таким образом, каждый Проблема, которую можно решить с помощью алгоритмов суффиксного дерева, также может быть решена с помощью расширенный массив суффиксов.^[2]

Решаем, если узор ${ displaystyle P}$ длины ${ displaystyle m}$ это подстрока строки ${ displaystyle S}$ длины ${ displaystyle n}$ берет ${ Displaystyle О (м журнал п)}$ время, если используется только массив суффиксов. Путем дополнительного использования информации LCP эту границу можно улучшить до ${ Displaystyle О (м + журнал п)}$ время.^[3] Абуэльода, Курц и Охлебуш (2004) покажите, как еще больше улучшить это время работы для достижения оптимального ${ Displaystyle О (м)}$ время. Таким образом, используя массив суффиксов и информацию о массиве LCP, на запрос решения можно ответить так же быстро, как с помощью суффиксное дерево.

Массив LCP также является неотъемлемой частью сжатых деревьев суффиксов, которые обеспечивают полную функциональность дерева суффиксов, такую как ссылки суффиксов и наименьший общий предок запросы.^[5]^[6] Кроме того, его можно использовать вместе с массивом суффиксов для вычисления Лемпеля-Зива. LZ77 факторизация в ${ Displaystyle О (п)}$ время.^[2]^[7]^[8]^[9]

В проблема с самой длинной повторяющейся подстрокой для строки ${ displaystyle S}$ длины ${ displaystyle n}$ можно решить в ${ Displaystyle Theta (п)}$ время, используя массив суффиксов ${ displaystyle A}$ и массив LCP. Достаточно провести линейное сканирование по массиву LCP, чтобы найти его максимальное значение ${ displaystyle v_ {max}}$ и соответствующий индекс ${ displaystyle i}$ куда ${ displaystyle v_ {max}}$ хранится. Самая длинная подстрока, встречающаяся не менее двух раз, тогда определяется как ${ Displaystyle S [A [я], A [я] + v_ {max} -1]}$ .

В оставшейся части этого раздела более подробно рассматриваются два применения массива LCP: как можно использовать массив суффиксов и массив LCP строки для построения соответствующего дерева суффиксов и как можно отвечать на запросы LCP для произвольных суффиксов с использованием диапазона минимум запросов к массиву LCP.

Найдите количество вхождений шаблона

Чтобы найти количество вхождений данной строки ${ displaystyle P}$ (длина ${ displaystyle m}$ ) в тексте ${ displaystyle T}$ (длина ${ displaystyle N}$ ),^[3]

Мы используем двоичный поиск по суффиксному массиву ${ displaystyle T}$ чтобы найти начальную и конечную позиции всех вхождений ${ displaystyle P}$ .
Теперь для ускорения поиска мы используем массив LCP, а именно специальную версию массива LCP (ниже LCP-LR).

Проблема с использованием стандартного двоичного поиска (без информации LCP) заключается в том, что в каждом из ${ Displaystyle О ( журнал N)}$ Чтобы выполнить сравнения, мы сравниваем P с текущей записью массива суффиксов, что означает полное сравнение строк длиной до m символов. Итак, сложность ${ Displaystyle О (м журнал N)}$ .

Массив LCP-LR помогает улучшить это до ${ Displaystyle О (м + журнал N)}$ , следующим образом:

На любом этапе алгоритма двоичного поиска мы, как обычно, рассматриваем диапазон ${ Displaystyle (L, точки, R)}$ суффиксного массива и его центральной точки ${ displaystyle M}$ , и решим, будем ли мы продолжать поиск в левом поддиапазоне ${ Displaystyle (L, точки, M)}$ или в правом поддиапазоне ${ Displaystyle (М, точки, R)}$ . Чтобы принять решение, мы сравниваем ${ displaystyle P}$ к строке на ${ displaystyle M}$ . Если ${ displaystyle P}$ идентичен ${ displaystyle M}$ , наш поиск завершен. Но если нет, то мы уже сравнили первые ${ displaystyle k}$ персонажи ${ displaystyle P}$ а потом решил, будет ли ${ displaystyle P}$ лексикографически меньше или больше, чем ${ displaystyle M}$ . Предположим, результат таков, что ${ displaystyle P}$ больше чем ${ displaystyle M}$ . Итак, на следующем этапе мы рассмотрим ${ Displaystyle (М, точки, R)}$ и новая центральная точка ${ displaystyle M '}$ в середине:

             M ...... M '...... R | мы знаем: lcp (P, M) == k

Уловка теперь заключается в том, что LCP-LR предварительно вычисляется так, что ${ displaystyle O (1)}$ -lookup сообщает нам самый длинный общий префикс ${ displaystyle M}$ и ${ displaystyle M '}$ , ${ Displaystyle mathrm {lcp} (М, М ')}$ .

Мы уже знаем (из предыдущего шага), что ${ displaystyle M}$ сам имеет префикс ${ displaystyle k}$ общие персонажи с ${ displaystyle P}$ : ${ Displaystyle mathrm {lcp} (P, M) = k}$ . Теперь есть три возможности:

Случай 1: ${ Displaystyle к < mathrm {lcp} (М, М ')}$ , т.е. ${ displaystyle P}$ имеет меньше префиксных символов, общих с M, чем M имеет общих с M '. Это означает, что (k + 1) -й символ M 'совпадает с символом M, и поскольку P лексикографически больше M, он также должен быть лексикографически больше M'. Итак, продолжаем в правой половине (М ', ..., R).
Случай 2: ${ Displaystyle к> mathrm {lcp} (М, М ')}$ , т.е. ${ displaystyle P}$ имеет больше символов префикса, общих с ${ displaystyle M}$ чем ${ displaystyle M}$ имеет общее с ${ displaystyle M '}$ . Следовательно, если бы мы сравнили ${ displaystyle P}$ к ${ displaystyle M '}$ , общий префикс будет меньше, чем ${ displaystyle k}$ , и ${ displaystyle M '}$ будет лексикографически больше, чем ${ displaystyle P}$ , поэтому, фактически не делая сравнения, продолжаем в левой половине ${ Displaystyle (М, точки, М ')}$ .
Случай 3: ${ Displaystyle к = mathrm {lcp} (М, М ')}$ . Итак, M и M 'идентичны ${ displaystyle P}$ во-первых ${ displaystyle k}$ символы. Чтобы решить, продолжаем ли мы левую или правую половину, достаточно сравнить ${ displaystyle P}$ к ${ displaystyle M '}$ начиная с ${ Displaystyle (к + 1)}$ й персонаж.
Продолжаем рекурсивно.

Общий эффект заключается в том, что ни один персонаж ${ displaystyle P}$ сравнивается с любым символом текста более одного раза. Общее количество сравнений символов ограничено ${ displaystyle m}$ , поэтому общая сложность действительно ${ Displaystyle О (м + logN)}$ .

Нам все еще нужно предварительно вычислить LCP-LR, чтобы он мог сказать нам ${ displaystyle O (1)}$ время lcp между любыми двумя записями массива суффиксов. Мы знаем, что стандартный массив LCP дает нам lcp только последовательных записей, т.е. ${ Displaystyle mathrm {lcp} (я-1, я)}$ для любого ${ displaystyle i}$ . Тем не мение, ${ displaystyle M}$ и ${ displaystyle M '}$ в приведенном выше описании не обязательно являются последовательными записями.

Ключ к этому - понять, что только определенные диапазоны ${ Displaystyle (L, точки, R)}$ никогда не произойдет во время двоичного поиска: он всегда начинается с ${ Displaystyle (0, точки, N)}$ и делит это в центре, а затем продолжает влево или вправо и снова делит эту половину и так далее. Другой способ взглянуть на это: каждая запись массива суффиксов возникает как центральная точка ровно одного возможного диапазона во время двоичного поиска. Таким образом, существует ровно N различных диапазонов ${ Displaystyle (L точки M точки R)}$ что может сыграть роль во время двоичного поиска, и достаточно предварительно вычислить ${ Displaystyle mathrm {lcp} (L, M)}$ и ${ Displaystyle mathrm {lcp} (М, R)}$ для тех ${ displaystyle N}$ возможные диапазоны. Так что это ${ displaystyle 2N}$ различные предварительно вычисленные значения, поэтому LCP-LR ${ Displaystyle О (Н)}$ по размеру.

Более того, существует простой рекурсивный алгоритм для вычисления ${ displaystyle 2N}$ значения LCP-LR в ${ Displaystyle О (Н)}$ время из стандартного массива LCP.

Подводить итоги:

Можно вычислить LCP-LR в ${ Displaystyle О (Н)}$ время и ${ Displaystyle О (2N) = О (N)}$ пространство из ЛКП.
Использование LCP-LR во время двоичного поиска помогает ускорить процедуру поиска с ${ Displaystyle О (М журнал N)}$ к ${ Displaystyle О (М + logN)}$ .
Мы можем использовать два бинарных поиска, чтобы определить левый и правый конец диапазона соответствия для ${ displaystyle P}$ , а длина диапазона совпадений соответствует количеству вхождений для P.

Построение суффиксного дерева

Учитывая массив суффиксов ${ displaystyle A}$ и массив LCP ${ displaystyle H}$ строки ${ Displaystyle S = s_ {1}, s_ {2}, ldots s_ {n} $}$ длины ${ displaystyle n + 1}$ , его суффиксное дерево ${ displaystyle ST}$ может быть построен в ${ Displaystyle О (п)}$ time на основе следующей идеи: начните с частичного дерева суффиксов для лексикографически наименьшего суффикса и несколько раз вставляйте другие суффиксы в порядке, заданном массивом суффиксов.

Позволять ${ displaystyle ST_ {i}}$ быть частичным суффиксным деревом для ${ Displaystyle 0 Leq я Leq п}$ . Далее пусть ${ displaystyle d (v)}$ быть длиной конкатенации всех меток пути от корня ${ displaystyle ST_ {i}}$ узел ${ displaystyle v}$ .

Случай 1 (

{ Displaystyle d (v) = H [я + 1]}

): Предположим, что суффиксы

{ Displaystyle а $}

,

{ displaystyle ana $}

,

{ Displaystyle анана $}

и

{ displaystyle банан $}

строки

{ Displaystyle S = банан $}

уже добавлены в суффиксное дерево. Тогда суффикс

{ displaystyle na $}

добавляется к дереву, как показано на рисунке. В крайний правый путь выделен красным.

Начать с ${ displaystyle ST_ {0}}$ , дерево, состоящее только из корня. Вставить ${ Displaystyle А [я + 1]}$ в ${ displaystyle ST_ {i}}$ , иди вверх по крайний правый путь, начинающийся с недавно вставленного листа ${ Displaystyle А [я]}$ к корню, до самого глубокого узла ${ displaystyle v}$ с ${ Displaystyle d (v) Leq H [я + 1]}$ достигнуто.

Нам нужно различать два случая:

${ Displaystyle d (v) = H [я + 1]}$ : Это означает, что объединение меток на корне- ${ displaystyle v}$ путь равен самому длинному общему префиксу суффиксов ${ Displaystyle А [я]}$ и ${ Displaystyle А [я + 1]}$ .
В этом случае вставьте ${ Displaystyle А [я + 1]}$ как новый лист ${ displaystyle x}$ узла ${ displaystyle v}$ и обозначьте край ${ displaystyle (v, x)}$ с ${ Displaystyle S [A [я + 1] + Н [я + 1], п]}$ . Таким образом, метка края состоит из оставшихся символов суффикса ${ Displaystyle А [я + 1]}$ которые еще не представлены конкатенацией меток корня к ${ displaystyle v}$ дорожка.
Это создает частичное дерево суффиксов ${ Displaystyle ST_ {я + 1}}$ .

Случай 2 ( ${ Displaystyle d (v) <Ч [я + 1]}$ ): Чтобы добавить суффикс ${ displaystyle nana $}$ , край к ранее вставленному суффиксу ${ displaystyle na $}$ должен быть разделен. Новое ребро нового внутреннего узла помечается самым длинным общим префиксом суффиксов. ${ displaystyle na $}$ и ${ displaystyle nana $}$ . Края, соединяющие два листа, помечены осталось символы суффикса, не являющиеся частью префикса.
${ Displaystyle d (v) <Ч [я + 1]}$ : Это означает, что объединение меток на корне- ${ displaystyle v}$ path отображает меньше символов, чем самый длинный общий префикс суффиксов ${ Displaystyle А [я]}$ и ${ Displaystyle А [я + 1]}$ и отсутствующий символы содержатся в метке края ${ displaystyle v}$ с крайний правый край. Следовательно, мы должны разделить этот край следующим образом:
Позволять ${ displaystyle w}$ быть ребенком ${ displaystyle v}$ на ${ displaystyle ST_ {i}}$ крайний правый путь.

Удалить край ${ displaystyle (v, w)}$ .
Добавить новый внутренний узел ${ displaystyle y}$ и новый край ${ displaystyle (v, y)}$ с этикеткой ${ Displaystyle S [A [я] + d (v), A [я] + H [я + 1] -1]}$ . Новая этикетка состоит из отсутствующий символы самого длинного общего префикса ${ Displaystyle А [я]}$ и ${ Displaystyle А [я + 1]}$ . Таким образом, конкатенация меток корня к ${ displaystyle y}$ путь теперь отображает самый длинный общий префикс ${ Displaystyle А [я]}$ и ${ Displaystyle А [я + 1]}$ .
Соединять ${ displaystyle w}$ к вновь созданному внутреннему узлу ${ displaystyle y}$ по краю ${ Displaystyle (у, ш)}$ что помечено ${ Displaystyle S [A [я] + Н [я + 1], A [я] + d (ш) -1]}$ . Новая этикетка состоит из осталось символы удаленного края ${ displaystyle (v, w)}$ которые не использовались в качестве метки края ${ displaystyle (v, y)}$ .
Добавлять ${ Displaystyle А [я + 1]}$ как новый лист ${ displaystyle x}$ и подключите его к новому внутреннему узлу ${ displaystyle y}$ по краю ${ Displaystyle (у, х)}$ что помечено ${ Displaystyle S [A [я + 1] + Н [я + 1], п]}$ . Таким образом, метка края состоит из оставшихся символов суффикса ${ Displaystyle А [я + 1]}$ которые еще не представлены конкатенацией меток корня к ${ displaystyle v}$ дорожка.
Это создает частичное дерево суффиксов ${ Displaystyle ST_ {я + 1}}$ .

Простой аргумент амортизации показывает, что время работы этого алгоритма ограничено ${ Displaystyle О (п)}$ :

Узлы, которые проходят на шаге ${ displaystyle i}$ поднявшись по крайний правый путь ${ displaystyle ST_ {i}}$ (кроме последнего узла ${ displaystyle v}$ ) удалены из крайний правый путь, когда ${ Displaystyle А [я + 1]}$ добавляется к дереву как новый лист. Эти узлы больше никогда не будут пройдены на всех последующих этапах. ${ displaystyle j> i}$ . Следовательно, самое большее ${ displaystyle 2n}$ узлы будут пройдены полностью.

LCP запросы для произвольных суффиксов

Массив LCP ${ displaystyle H}$ содержит только длину самого длинного общего префикса каждой пары последовательных суффиксов в массиве суффиксов ${ displaystyle A}$ . Однако с помощью массива обратных суффиксов ${ displaystyle A ^ {- 1}}$ ( ${ Displaystyle A [я] = j Leftrightarrow A ^ {- 1} [j] = i}$ , т.е. суффикс ${ displaystyle S [j, n]}$ что начинается с позиции ${ displaystyle j}$ в ${ displaystyle S}$ хранится в позиции ${ displaystyle A ^ {- 1} [j]}$ в ${ displaystyle A}$ ) и постоянного времени минимальный диапазон запросов на ${ displaystyle H}$ , можно определить длину самого длинного общего префикса произвольных суффиксов в ${ displaystyle O (1)}$ время.

Из-за лексикографического порядка массива суффиксов каждый общий префикс суффиксов ${ Displaystyle S [я, п]}$ и ${ displaystyle S [j, n]}$ должен быть общим префиксом для всех суффиксов между ${ displaystyle i}$ позиция в массиве суффиксов ${ displaystyle A ^ {- 1} [я]}$ и ${ displaystyle j}$ позиция в массиве суффиксов ${ displaystyle A ^ {- 1} [j]}$ . Следовательно, длина самого длинного префикса, который разделяет все из этих суффиксов - минимальное значение в интервале ${ Displaystyle Н [A ^ {- 1} [я] + 1, A ^ {- 1} [j]]}$ . Это значение можно найти в постоянное время, если ${ displaystyle H}$ предварительно обрабатывается для запросов с минимальным диапазоном.

Таким образом, данная строка ${ displaystyle S}$ длины ${ displaystyle n}$ и две произвольные позиции ${ displaystyle i, j}$ в строке ${ displaystyle S}$ с ${ Displaystyle A ^ {- 1} [я]$ , длина самого длинного общего префикса суффиксов ${ Displaystyle S [я, п]}$ и ${ displaystyle S [j, n]}$ можно вычислить следующим образом: ${ displaystyle operatorname {LCP} (i, j) = H [ operatorname {RMQ} _ {H} (A ^ {- 1} [i] + 1, A ^ {- 1} [j])]}$ .

Примечания

внешняя ссылка

Зеркало ad-hoc-реализации кода описано в Фишер (2011)
SDSL: краткая библиотека структур данных - предоставляет различные реализации массивов LCP, структуры поддержки запроса минимального диапазона (RMQ) и многие другие краткие структуры данных
Обход дерева суффиксов снизу вверх, эмулируемый с использованием массива суффиксов и массива LCP (Java)
Проект индексирования текста (построение суффиксных деревьев, массивов суффиксов, массива LCP и Преобразование Барроуза-Уиллера )

[FOOTNOTEKasaiLeeArimuraArikawa2001-1] Kasai et al. 2001 г..

[FOOTNOTEAbouelhodaKurtzOhlebusch2004-2] а ^б ^c Абуэльода, Курц и Охлебуш 2004.

[FOOTNOTEManberMyers1993-3] а ^б ^c ^d Манбер и Майерс 1993.

[FOOTNOTEOhlebuschFischerGog2010-4] Охлебуш, Фишер и Гог, 2010 г..

[FOOTNOTESadakane2007-5] Садакане 2007.

[FOOTNOTEFischerMäkinenNavarro2009-6] Фишер, Мякинен и Наварро, 2009 г..

[FOOTNOTECrochemoreIlie2008-7] Крошмор и Илие 2008.

[FOOTNOTECrochemoreIlieSmyth2008-8] Crochemore, Ilie & Smyth, 2008 г..

[FOOTNOTEChenPuglisiSmyth2008-9] Чен, Пуглиси и Смит 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

LCP массив
Тип	Множество
Изобретенный	Манбер и Майерс (1990)
Сложность времени и космическая сложность в нотация большой O
	Средний	Худший случай
Космос	${ Displaystyle { mathcal {O}} (п)}$	${ Displaystyle { mathcal {O}} (п)}$
Строительство	${ Displaystyle { mathcal {O}} (п)}$	${ Displaystyle { mathcal {O}} (п)}$