In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations.
The construction of such a tree for the string \(S\) takes time and space linear in the length of \(S\).
How to build a Suffix tree
Bibliography
“Suffix Tree.” 2022. Wikipedia, November. https://en.wikipedia.org/w/index.php?title=Suffix_tree&oldid=1121139308.