The minimum DAWG for all suffixes of a string and its applications

Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara, Hiromasa Hoshino, Setsuo Arikawa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)


For a string w over an alphabet Σ, we consider a composite data structure called the all-suffixes directed acyclic word graph (ASDAWG). ASDAWG (w) has |w| + 1 initial nodes, and the dag induced by all reachable nodes from the k-th initial node conforms with DAWG(w[k :]), where w[k :] denotes the k-th suffix of w. We prove that the size of the minimum ASDAWG(w) (MASDAWG(w)) is Θ(|w|2) for |Σ| = 1, and is Θ(|w|) for |Σ| ≥ 2. Moreover, we introduce an on-line algorithm which directly constructs MASDAWG(w) for given w, whose running time is linear with respect to its size. We also demonstrate some application problems, beginning-sensitive pattern matching, region-sensitive pattern matching, and VLDC-pattern matching, for which AS-DAWGs are useful.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 13th Annual Symposium, CPM 2002, Proceedings
EditorsAlberto Apostolico, Masayuki Takeda
PublisherSpringer Verlag
Number of pages15
ISBN (Electronic)9783540438625
Publication statusPublished - 2002
Event13th Annual Symposium on Combinatorial Pattern Matching, CPM 2002 - Fukuoka, Japan
Duration: Jul 3 2002Jul 5 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th Annual Symposium on Combinatorial Pattern Matching, CPM 2002

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The minimum DAWG for all suffixes of a string and its applications'. Together they form a unique fingerprint.

Cite this