The Prague Stringology Club Workshop '98
Zdeněk Troníček and Bořivoj Melichar
Directed Acyclic Subsequence Graph
| Abstract: |
| Directed Acyclic Subsequence Graph is an automaton, which accepts all subsequences of the given string. We introduce a left-to-right algorithm for incremental construction of DASG. The algorithm requires O(z) extra space and O(nz.log(z)) time for arbitrary alphabet O(nz) for fixed alphabet), where z=min(|A|,n). The number of transitions can be reduced by encoding input symbols using k digits, where k < min(|A|,n). We introduce a left-to-right algorithm for incremental construction of DASG for k=2. We show the extension of the algorithm for the set of strings and its application for the longest common subsequence problem. |
| Download paper: |  |
 |
| PostScript |