Back to Search
Start Over
Constrained Longest Common Subsequences with Run-Length-Encoded Strings.
- Source :
- Computer Journal; May2015, Vol. 58 Issue 5, p1074-1084, 11p
- Publication Year :
- 2015
-
Abstract
- Given two strings X and Y and a constraining string P, a string Z is called a constrained longest common subsequence of X and Y with respect to P if Z is the longest common subsequence of X and Y such that P is a subsequence of Z. In this paper, we propose an O(r x min{mN, nM})-time algorithm for solving this problem, where m, n and r are the lengths of X, Y and P, respectively, and M and N are the number of runs of the run-length-encoded strings of X and Y, respectively. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00104620
- Volume :
- 58
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Computer Journal
- Publication Type :
- Academic Journal
- Accession number :
- 102474969
- Full Text :
- https://doi.org/10.1093/comjnl/bxu012