Как построить суффикс Trie для всех подстрок строки?

Question

Я хочу построить пространственный эффективный суффикс trie для всех подстрок строки; Предположим, что длина строки равна 5000, тогда число подстрок будет около 25 * 10^6 и для каждого узла im, хранящего массив linkd размером 26 , поэтому общая память = 26 * 5000 * 5000, что невозможно. Ожидается ошибка времени выполнения. У меня есть решение для пространственного эффективного суффикса trie, в котором мы сжимаем путь, где у нас нет chooices, поэтому порядок пространства приблизительно становится линейным. Но я не могу понять, может ли кто-нибудь помочь мне в этом.

Answer 1

Вы не ищите trie, вместо этого для дерева суффикса, я думаю. Сжатие пути - это путь, но я бы просто искал алгоритм Укконена. Сложность времени и пространства равна n. Если вам нужно что-то, что лучше понять, просто найдите Суффикс-массивы. Сложность пространства равна n, а нижняя константа (около 6 вместо 32 или около того, я не помню точно цифры) и намного лучше прогнозирования кэша через аппаратное обеспечение.

Answer 2

Не уверен в вашей арифметике ... но если у вас есть только одна строка, ваше дерево должно быть размером 26n.

Технически вы можете заменить Suffix Trie/Tree массивом Suffix Array + LCP, поддерживая ту же скорость операций с основным графиком. Потребление памяти будет 1 + 4 + 4 = 9n. Недостатком является то, что изменить исходную строку непросто.