论文标题
更快的Str-EC-LCS计算
Faster STR-EC-LCS Computation
论文作者
论文摘要
最长的常见子序列（LCS）问题是弦乐学中的一个核心问题，它找到了给定两个字符串$ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a和$ b $的最长常见子序列。最近，Chen和Chao提出了一组四个受约束的LCS问题（称为广义约束LCS问题）[J. J.梳子。 Optim，2011]。在本文中，我们考虑了划定的约束LCS（Str-EC-LCS）问题。据说字符串$ z $是两个给定字符串$ a $ a $ a $ a $ a $ a $ a $ a $ p $的str-ec-lcs，如果$ z $是$ z $的最长常见子序列之一，$ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a和$ b $不包含$ p $作为基因。 Wang等。提出了一种动态编程解决方案，该解决方案计算$ O（MNR）$时间和空间中的Str-EC-LCS，其中$ m = | a |，n = | b |，r = | p | $ [inf。过程。 Lett。，2013]。在本文中，我们为Str-EC-LCS问题展示了一种新解决方案。我们的算法在$ O（n |σ|+（L+1）（M-L+1）R中计算str-ec-lcs $ |σ| \ leq \ min \ {m，n \} $表示在$ a $ a和$ b $中出现的不同字符集，而$ l $是str-ec-lcs的长度。该算法比$ O（MNR）$ - 时间算法的短/长str-ec-lcs（即$ l \ in O（1）$（1）$或$ m-l \ in O（1）$），并且至少与所有情况的$ O（MNR）$ - TIME ALGORITM一样高。
The longest common subsequence (LCS) problem is a central problem in stringology that finds the longest common subsequence of given two strings $A$ and $B$. More recently, a set of four constrained LCS problems (called generalized constrained LCS problem) were proposed by Chen and Chao [J. Comb. Optim, 2011]. In this paper, we consider the substring-excluding constrained LCS (STR-EC-LCS) problem. A string $Z$ is said to be an STR-EC-LCS of two given strings $A$ and $B$ excluding $P$ if, $Z$ is one of the longest common subsequences of $A$ and $B$ that does not contain $P$ as a substring. Wang et al. proposed a dynamic programming solution which computes an STR-EC-LCS in $O(mnr)$ time and space where $m = |A|, n = |B|, r = |P|$ [Inf. Process. Lett., 2013]. In this paper, we show a new solution for the STR-EC-LCS problem. Our algorithm computes an STR-EC-LCS in $O(n|Σ| + (L+1)(m-L+1)r)$ time where $|Σ| \leq \min\{m, n\}$ denotes the set of distinct characters occurring in both $A$ and $B$, and $L$ is the length of the STR-EC-LCS. This algorithm is faster than the $O(mnr)$-time algorithm for short/long STR-EC-LCS (namely, $L \in O(1)$ or $m-L \in O(1)$), and is at least as efficient as the $O(mnr)$-time algorithm for all cases.
