Loading...
Please wait, while we are loading the content...
Similar Documents
Algorithms for computing the longest parameterized common subsequence.
| Content Provider | CiteSeerX |
|---|---|
| Author | Iliopoulos, Costas S. Kubica, Marcin Rahman, M. Sohel |
| Abstract | Abstract. In this paper, we revisit the classic and well-studied longest common subsequence (LCS) problem and study some new variants, first introduced and studied by Rahman and Iliopoulos [Algorithms for Computing Variants of the Longest Common Subsequence Problem, ISAAC 2006]. Here we define a generalization of these variants, the longest parameterized common subsequence (LPCS) problem, and show how to solve it in O(n 2)andO(n + R log n) time. Furthermore, we show how to compute two variants of LCS, RELAG and RIFIG in O(n + R) time. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Parameterized Common Subsequence Well-studied Longest Common Subsequence Longest Common Subsequence Problem Iliopoulos Algorithm New Variant |
| Content Type | Text |
| Resource Type | Article |
