Finite automata based algorithms on subsequences and supersequences of degenerate strings |
| |
| Authors: | Costas Iliopoulos M Sohel Rahman Michal Voráček Ladislav Vagner |
| |
| Institution: | 1. Algorithm Design Group, Department of Computer Science, King''s College London, Strand, London WC2R 2LS, United Kingdom;2. Department of Computer Science & Engineering, Czech Technical University, Czech Republic |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
