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 |