Здравствуйте)
Требуется построить для строки суффиксное дерево. Прочитала литературу по этому поводу, однако не совсем все понятно.
Хотела бы посоветоваться каким из имеющихся алгоритмов лучше воспользоваться? (какой легче)
И с самого начала возникает вопрос: как описать структуру? Использовать две структуры, одна из которых будет описывать узлы дерева, а другая ребра ?или как?
в общем помогите пожалуйста разобраться)
Заранее спасибо)
http://cs.mipt.ru/wiki/index.php/Суффиксное_дерево
не годится разве?
Там даже готовый код есть.
То, что там есть какой-то код - еще не значит, что он правильный. В РУнете с суффиксными деревьями вообще огромная проблема - алгоритмы перевираются нещадно, такое ощущение - что все делается для того, чтоб как-то сляпать программу хоть сколько-нибудь работоспособную, и сдать её, и все, на этом дело заканчивается.
Поэтому искать информацию о суффиксных деревьях лучше всего на англоязычных сайтах. Там, по крайней мере, будет правильно описан алгоритм и последовательность действий.
По поводу какой алгоритм лучше - МакКейт быстрее, чем Укконен (по крайней мере, почти все реализации алгоритма МакКейта работают быстрее, чем реализации алгоритма Укконена). Есть еще Вайнер, который тоже очень неплох.
Реализаций (правильных реализаций, хотелось бы заметить) алгоритмов построения суффиксного дерева на Паскале/Дельфи я вообще не встречал. С++ есть. Вроде и на чистом С где-то было... На Ассемблере тоже есть...