can also be stored compactly suffix tries one of the primary applications for tries is for the case when the strings in the collection are all the suffixes of string such trie is called the suffix trie (also known as suffix tree or position treeof string for examplefigure shows the suffix trie for the eight suffixes of string "minimize for suffix triethe compact representation presented in the previous section can be further simplified namelythe label of each vertex is pair ( ,jindicating the string [ (see figure to satisfy the rule that no suffix of is prefix of another suffixwe can add special characterdenoted with $that is not in the original alphabet at the end of (and thus to every suffixthat isif string has length nwe build trie for the set of strings [ ]$for , saving space using suffix trie allows us to save space over standard trie by using several space compression techniquesincluding those used for the compressed trie the advantage of the compact representation of tries now becomes apparent for suffix tries since the total length of the suffixes of string of length is storing all the suffixes of explicitly would take ( space even sothe suffix trie represents these strings implicitly in (nspaceas formally stated in the following proposition proposition the compact representation of suffix trie for string of length uses (nspace construction we can construct the suffix trie for string of length with an incremental algorithm like the one given in section this construction takes (dn time because the total length of the suffixes is quadratic in howeverthe (compactsuffix trie for string of length can be constructed in (ntime with specialized algorithmdifferent from the one for general tries this linear-time construction algorithm is fairly complexhoweverand is not reported here stillwe can take advantage of the existence of this fast construction algorithm when we want to use suffix trie to solve other problems