Самая длинная общая проблема подстроки согласно вики может быть решена с помощью дерева суффиксов.
Из вики:
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
опущены из-за пробела):
Самая длинная общая подстрока - ABC
, но это не так. Я не вижу, как здесь помогает описание вики.ABC
не самые глубокие внутренние узлы с листовыми узлами.
Любая помощь, чтобы понять, как это работает?