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

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

The longest common substrings of a set of strings can be found by building a generalised suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it

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

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

14
задан Cratylus 12 June 2012 в 20:14
поделиться