suffix tree vs trie

Хотя бы чтобы не разворачивать строки? Плюс, зависит от характера данных.

Забыл добавить: под префиксным деревом я имею ввиду сжатое (компактное) префиксное дерево

Для словарей оно нужно.

Так и сжатое суффиксное дерево для перевернутой строки будет не хуже для поиска 'перевернутого' слова в ней

Может быть дело в том что prefix tree не нужно перестраивать для добавления нового слова в строку?

Тип того. И вроде как есть различие в их назначении: префиксные - для словаря, суффиксные - для нахождения подстрок (наидлиннейшей подстроки)

педогрек как обычно блещет умом

Продолжайте наблюдения

Trie — это то, что по-русски обычно называют бором, и оно хранит множество образцов, а suffix tree — это его сжатая версия, построенная на всех суффиксах одной строки (хотя можно засунуть и несколько). Для его построения за линию переворачивать ничего не нужно.

Из trie делают автомат для поиска всех вхождений множества образцов в текст — алгоритм Ахо-Корасик