Suffix automaton
In computer science, a suffix automaton or directed acyclic word graph is a finite automaton that recognizes the set of suffixes of a given string. It can be thought of as a compressed form of the suffix tree, a data structure that efficiently represents the suffixes of the 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]
Suffix automata have applications in approximate string matching.[1]
See also
References
<templatestyles src="Reflist/styles.css" />
Cite error: Invalid <references> tag; parameter "group" is allowed only.
<references />, or <references group="..." />Additional reading
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found.
<templatestyles src="Asbox/styles.css"></templatestyles>
 |
This computer science article is a stub. You can help Wikipedia by expanding it. |
