TY - GEN

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

AU - Inenaga, Shunsuke

AU - Takeda, Masayuki

AU - Shinohara, Ayumi

AU - Hoshino, Hiromasa

AU - Arikawa, Setsuo

PY - 2002/1/1

Y1 - 2002/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=23044534111&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23044534111&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:23044534111

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 153

EP - 167

BT - Combinatorial Pattern Matching - 13th Annual Symposium, CPM 2002, Proceedings

A2 - Apostolico, Alberto

A2 - Takeda, Masayuki

PB - Springer-Verlag

T2 - 13th Annual Symposium on Combinatorial Pattern Matching, CPM 2002

Y2 - 3 July 2002 through 5 July 2002

ER -