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 article: Article in PostScript Article in PDF
 PostScript   PDF