Является ли дерево суффиксов уникальным?

Я работаю над алгоритмом дерева суффиксов в биоинформатике. Я хочу знать, уникально ли дерево суффиксов?

Например ,

String str = "xabaxe"

Эта строка или другие примеры строк имеют альтернативное дерево суффиксов?


algorithm bioinformatics suffix-tree
person seniorc    schedule 30.10.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Он всегда уникален. Каждому пути от корня к листу соответствует суффикс. Дерево однозначно определяется всеми путями от корня к листьям, потому что степень любого внутреннего узла не меньше 2 (по определению суффиксного дерева). Но достаточности однозначно определяются строкой. Таким образом, для любой строки существует одно и только одно дерево суффиксов.

person kraskevich    schedule 30.10.2014
comment
что, если конец искомой подстроки находится в листе. Точнее, на префиксе листа. В этом примере, например, если мы ищем ab, который является суффиксом строки str, будет ли алгоритм дерева суффиксов поиска возвращать совпадение? Поскольку ab заканчивается на листе abaxe - person curious; 15.01.2016