Constrained Longest Common Subsequences with Run-Length-Encoded Strings
Constrained Longest Common Subsequences with Run-Length-Encoded Strings
复制标题
具有游程编码字符串的约束最长公共子序列
DOI：
10.1093/comjnl/bxu012
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Yu
中科院分区：
文献类型：
--
作者：
J. J. Liu;Yue;Yu
给定两个字符串x和y和一个约束字符串p，如果z是x和y的最长常见子序列，则称为x和y的约束最长的公共子序列，使得p是z的子序列。在本文中，我们提出了一个o（r×min {mn，nm}） - 用于解决此问题的时间算法，其中m，n和r分别是x，y和p的长度，而m和m是m和n运行长度编码的运行次数X和Y的字符串。
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×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.