Name
Abstract | ||
|---|---|---|
The directed acyclic word graph (DAWG) of a string y is the smallest (partial) DFA which recognizes all suffixes of y and has only O(n) nodes and edges. We present the first O(n)-time algorithm for computing the DAWG of a given string y of length n over an integer alphabet of polynomial size in n. We also show that a straightforward modification to our DAWG construction algorithm leads to the first O(n)-time algorithm for constructing the affix tree of a given string y over an integer alphabet. Affix trees are a text indexing structure supporting bidirectional pattern searches. As an application to our O(n)-time DAWG construction algorithm, we show that the set MAW(y) of all minimal absent words of y can be computed in optimal O(n + |MAW(y)|) time and O(n) working space for integer alphabets. |
Year | Venue | Field |
|---|---|---|
2016 | MFCS | Integer,Discrete mathematics,Affix,Combinatorics,Polynomial,Working space,Search engine indexing,Time complexity,Directed acyclic word graph,Mathematics,Alphabet |
DocType | Citations | PageRank |
Conference | 6 | 0.53 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuta Fujishige | 1 | 6 | 0.53 |
| Yuki Tsujimaru | 2 | 6 | 0.53 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 902 | 79.24 |