Constrained Longest Common Subsequences with Run-Length-Encoded Strings

被引：4

作者：

Liu, Jia-Jie ^{[1
]}

Wang, Yue-Li ^{[2
]}

Chiu, Yu-Shan ^{[1
]}

机构：

[1] Shih Hsin Univ, Dept Informat Management, Taipei 10607, Taiwan

[2] Natl Taiwan Univ Sci & Technol, Dept Informat Management, Taipei, Taiwan

来源：

COMPUTER JOURNAL | 2015年 / 58卷 / 05期

关键词：

longest common subsequence; constrained longest common subsequence; run-length-encoding; string compression; EDIT DISTANCE; ALGORITHM;

D O I：

10.1093/comjnl/bxu012

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：1074 / 1084

页数：11

共 17 条

[11] Fow E., 2000, INTRO DATA COMPRESSI
[12] Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
Freschi, V
Bogliolo, A
[J]. INFORMATION PROCESSING LETTERS, 2004, 90 (04) : 167 - 173
[13] New efficient algorithms for the LCS and constrained LCS problems
Iliopoulos, Costas S.
Rahman, M. Sohel
[J]. INFORMATION PROCESSING LETTERS, 2008, 106 (01) : 13 - 18
[14] Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
Liu, J. J.
Wang, Y. L.
Lee, R. C. T.
[J]. JOURNAL OF COMPLEXITY, 2008, 24 (02) : 173 - 184
[15] Edit distance for a run-length-encoded string and an uncompressed string
Liu, J. J.
Huang, G. S.
Wang, Y. L.
Lee, R. C. T.
[J]. INFORMATION PROCESSING LETTERS, 2007, 105 (01) : 12 - 16
[16] Sakai Y, 2012, LECT NOTES COMPUT SC, V7676, P197
[17] The constrained longest common subsequence problem
Tsai, YT
[J]. INFORMATION PROCESSING LETTERS, 2003, 88 (04) : 173 - 176

← 1 2 →