Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430614 | Journal of Discrete Algorithms | 2010 | 14 Pages |
Abstract
In this paper, we present linear-time algorithms for the construction two novel types of finite automata and show how they can be used to efficiently solve the Longest Common Subsequence (LCS), Shortest Common Supersequence (SCS) and Constrained Longest Common Subsequence (CLCS) problems for degenerate strings.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Costas Iliopoulos, M. Sohel Rahman, Michal Voráček, Ladislav Vagner,