Suffix automaton

Non-deterministic suffix automaton for the word "suffix". Epsilon transitions are shown grey.

In computer science, a suffix automaton is a data structure that efficiently represents the suffixes of a string. For example, a suffix automaton for the string "suffix" can be queried for other strings; it will report "true" for any of the strings "suffix", "uffix", "ffix", "fix", "ix" and "x", and "false" for any other string.[1] The suffix automaton of a set of strings U has at most 2Q − 2 states, where Q is the number of nodes of a prefix-tree representing the strings in U.[2]

A suffix automaton is a type of finite state machine. It can be regarded as a compressed suffix trie.

See also

References

  1. ↑ Navarro, Gonzalo (2001). "A guided tour to approximate string matching" (PDF). ACM Computing Surveys 33 (1): 31–88. doi:10.1145/375360.375365.
  2. ↑ Mohri, Mehryar; Moreno, Pedro; Weinstein, Eugene (September 2009). "General suffix automaton construction algorithm and space bounds". Theoretical Computer Science 410 (37): 3553–3562. doi:10.1016/j.tcs.2009.03.034.
This article is issued from Wikipedia - version of the Friday, October 23, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.