Я работаю над php-скриптом, который должен найти самую длинную повторяющуюся подстроку. Я нашел эту штуку Suffix-Tree. Я пытаюсь реализовать алгоритм Укконнена, но не могу понять, когда и как расширить дерево.
Ничего страшного, если у меня есть новый персонаж, которого нет в дереве, но мне нужно создать для него новый узел и отделить его от корня. Но как мне узнать, нужно ли разделить ребро?
Я нашел его реализацию на C++ (ссылка) и попытался перевести это на php, но я думаю, что у меня есть типо, потому что это дает почти хороший результат, проблема в том, что я не могу это исправить, пока не пойму его полностью...
Я прочитал с десяток описаний суффиксных деревьев, но некоторые из них не слишком углубляются в это, другие вызывают у меня головную боль после второго предложения.
Вот код, который у меня есть сейчас: Suffix-tree.php (извините, но этот редактор не смог его принять) Я использовал этот сайт, чтобы проверить результат.
Так что буду рад любому совету...
РЕДАКТИРОВАТЬ: я переписал его из материала JavaScript, найденного на упомянутом сайте. Вот ссылка на источник: Suffix-Tree v0.1