Почему мы не используем дерево префикса (trie), чтобы найти самую длинную общую подстроку?

Question

Недавно я изучаю, как использовать дерево для решения самой длинной общей проблемы с подстрокой. Изучив Wiki и другие онлайн-ресурсы, я обнаружил, что мы должны использовать дерево суффикса, чтобы найти самую длинную общую подстроку.

Как вики сказал:

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

Как Justin сказал:

String = ABCDE$XABCZ$ 
    End of word character 1 = $ 
    └── (0) 
     ├── (20) $ 
     ├── (22) ABC 
     │ ├── (15) DE$ 
     │ └── (23) Z$ 
     ├── (24) BC 
     │ ├── (16) DE$ 
     │ └── (25) Z$ 
     ├── (26) C 
     │ ├── (17) DE$ 
     │ └── (27) Z$ 
     ├── (18) DE$ 
     ├── (19) E$ 
     ├── (21) XABCZ$ 
     └── (28) Z$ 

В дереве суффиксов (компактных) вам необходимо найти самый глубокий внутренний узел (узлы), которые имеют листовые узлы из всех строк. Если у вас несколько узлов на одной глубине, вам нужно сравнить длину строки, представленной этим узлом. то есть ABC, BC и C имеют одинаковую глубину, поэтому вам нужно сравнить длину строк ABC, BC и C, чтобы увидеть, что больше; что, очевидно, является ABC.

Здесь я думал, что процесс поиска самых глубоких внутренних узлов, которые имеют узлы листа из всех строк, на самом деле является процессом поиска самого длинного общего префикса всех суффиксов из всех строк.

Так что вот вопрос: Почему мы не строим дерево префикса, в котором хранятся все суффиксы из всех строк? Затем мы можем найти дерево префикса, чтобы найти самый длинный общий префикс этих суффиксов. Я не могу сказать разницы между этими двумя. Может ли кто-нибудь дать мне некоторые подсказки, почему мы используем дерево суффикса вместо дерева префикса для решения этой проблемы?

Answer 1

Для суффиксов требуется только O(N) время и место для строки длиной N. Вот почему с его помощью можно решить самую длинную общую проблему подстроки в линейном времени.
Добавление всего количества строки в trie требует O(N^2) времени и пространства в худшем случае.

Так вы идете добавить все достаточное количество всех строк в trie на самом деле правильно, но неэффективно по сравнению с решением с деревом суффиксов.

Answer 2

Три слова используются для словаря. Он не хранит суффиксы.