Suffix Tree: реализация самой длинной повторяющейся подстроки

Question

Я реализовал дерево суффиксов, которое не сжимается. Я хотел знать, как решить проблему поиска самой длинной представляющей подстроки в строке. Я знаю, что мы должны найти самый глубокий внутренний узел с двумя дочерними элементами, но как это можно сделать? Кроме того, как мы узнаем, какая самая длинная повторяющаяся подстрока? Я заинтересован в коде в JAVA. Просьба дать реализацию Java. Для справки мой TrieNode выглядит как

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

Алгоритм Ахо-Корасика http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

Answer 2

Это только самый глубокий узел с двумя дочерними элементами, если вы храните конец байта строки.

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

Answer 3

Чтобы найти самый глубокий узел, можно также сделать BFS и выбрать узел, который имеет максимальный уровень.Я думаю, что узел с максимальным уровнем также является самым глубоким узлом. Тогда вы можете проверить, есть ли у него 2 потомка.иначе идти выше.не уверен, что это будет работать, хотя.какие-либо комментарии pps?