Как найти самую длинную общую подстроку, используя деревья?

Самая длинная общая проблема подстроки в соответствии с wiki может быть решена с использованием дерева суффикса. Из wiki:

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

Я не понимаю. Пример: если у меня есть:
ABCDE и XABCZ
то дерево суффикса (некоторые ветки из XABCZ опущены из-за пробела):
enter image description here

Самая длинная общая подстрока ABC, но я не вижу, как здесь описывается описание wiki.
ABC не является самым глубоким внутренним узлом с листовыми узлами.
Любая помощь, чтобы понять, как это работает?

Ответы

Ответ 1

Как и раньше, ваше дерево неверно.

Это то, что я получаю при запуске "ABCDE $XABCZ" через свой код.

Код дерева суффикса:

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$

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

Суффикс Trie code:

└── null
    ├── A
    │   └── B
    │       └── C
    │           ├── D
    │           │   └── (E) ABCDE
    │           └── (Z) ABCZ
    ├── B
    │   └── C
    │       ├── D
    │       │   └── (E) BCDE
    │       └── (Z) BCZ
    ├── C
    │   ├── D
    │   │   └── (E) CDE
    │   └── (Z) CZ
    ├── D
    │   └── (E) DE
    ├── (E) E
    ├── X
    │   └── A
    │       └── B
    │           └── C
    │               └── (Z) XABCZ
    └── (Z) Z

В (некомпактном) суффиксе trie найдите самый глубокий внутренний node (s), который имеет листовые узлы из всех строк.

Надеюсь, что это поможет.

Ответ 2

Фактически вы не нарисовали дерево суффикса. Если бы вы сделали это правильно, то в корне вы имели бы только всевозможные символы. Дерево разделяется только тогда, когда одна буква может иметь несколько следующих суффиксов. Это создает общие подстроки вместе в дереве, что делает их доступными.