Directed acyclic word graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, a directed acyclic word graph (DAWG) is a data structure that represents the set of all substrings of a string. As its name implies, a DAWG takes the form of a directed acyclic graph; it can also be viewed as a deterministic finite automaton, and is similar in structure to suffix trees. DAWG have applications in approximate string matching.[1]

See also[edit]


  1. ^ Navarro, Gonzalo (2001). "A guided tour to approximate string matching" (PDF). ACM Computing Surveys 33 (1): 31–88. doi:10.1145/375360.375365.