Дерево суффиксов: самая длинная реализация подстроки

Question

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

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

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

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

Answer 2

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

Answer 3

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