Suffix Tries
A suffix trie is a compressed trie containing all the suffixes of the given text.
- Suffix trees allow particularly fast implementations of many important string operations.
- Suffix trees can be constructed in O(n) time and space, where n is length of text, the algorithm for this is beyond the scope of this lecture!
- Once constructed, several operations can be performed quickly, for instance locating a substring, locating a substring if a certain number of mistakes are allowed, locating matches for a regular expression pattern etc.
The above example is from "Data Structures and Algorithms in Java"; Sixth Edition; Michael T. Goodrich, Roberto Tamassia and Michael H. Goldwasser; 2014; Wiley. and text from wikipedia.
|