On the generalized constrained longest common subsequence problems |
| |
| Authors: | Yi-Ching Chen Kun-Mao Chao |
| |
| Institution: | 1.Department of Computer Science and Information Engineering,National Taiwan University,Taipei,Taiwan;2.Department of Computer Science and Information Engineering, Graduate Institute of Biomedical Electronics and Bioinformatics, Graduate Institute of Networking and Multimedia,National Taiwan University,Taipei,Taiwan |
| |
| Abstract: | We investigate four variants of the longest common subsequence problem. Given two sequences X, Y and a constrained pattern P of lengths m, n, and ρ, respectively, the generalized constrained longest common subsequence (GC-LCS) problems are to find a longest common subsequence
of X and Y including (or excluding) P as a subsequence (or substring). We propose new dynamic programming algorithms for solving the GC-LCS problems in O(mn
ρ) time. We also consider the case where the number of constrained patterns is arbitrary. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
