How to construct a suffix Trie for all the substrings of a string?

Question

I want to build a space efficient suffix trie for all the substrings of the string; Suppose the length of the string is 5000, then number of substring would be approx 25*10^6 and for every node i m storing an array of linkd of size 26 so total memory = 26*5000*5000 which is not possible so runtime error is expected. I ve got a solution for a space efficient suffix trie in which we compress the path where we have no chooices so the order of space approximately becomes linear. But i m not able to understand so can anyone help me out of this.

Answer 1

You don't search for a trie, instead for a suffix tree I think. Compressing the path is a way, but I would just search for the Ukkonen algorithm. The Time and space complexity is n. If you want something which is better to understand, just search for Suffix Arrays. The space complexity is n as well, with a lower constant (about 6 instead of 32 or so, I don't remember the exactly numbers) and much better Cache prediction through the hardware.

Answer 2

Not sure about your arithmetic... but if you have only one string your tree must be 26n size.

Technically you can substitute Suffix Trie/Tree with Suffix Array + LCP Array maintaining the same speed of basic graph operations. The memory consumption will be 1 + 4 + 4 = 9n. The drawback is that it is not easy to change the original string.