In this paper we address the constrained longest common subsequence problem. Given two sequences $X$, $Y$ and a constrained sequence $P$, a sequence $Z$ is a constrained longest common subsequence for $X$ and $Y$ with respect to $P$ if $Z$ is the longest subsequence of $X$ and $Y$ such that $P$ is a subsequence of $Z$. Recently, Tsai \cite{Tsai} proposed an $O(n^2 \cdot m^2 \cdot r)$ time algorithm to solve this problem using dynamic programming technique, where $n$, $m$ and $r$ are the lengths of $X$, $Y$ and $P$, respectively. In this paper, we present a simple algorithm to solve the constrained longest common subsequence problem in $O(n \cdot m \cdot r)$ time and show that the constrained longest common subsequence problem is equivalent to a special case of the constrained multiple sequence alignment problem which can also be solved.


翻译:在本文中,我们处理受限制的最长共同后继问题。考虑到两个序列,即X美元、Y美元和受限制的后继问题,如果Z美元是X美元和Y美元这两个最长后继问题,那么,Z美元是受限制的最长共同后继问题。最近,Tsai\cite{Tsai}提议用一个美元(n_2\cdot m%2\cdot r) 时间算法,用动态程序技术解决这个问题,其中美元、美元和美元分别为X美元、美元和美元。在本文件中,我们提出了一个简单的算法,以解决美元(n\cdot m\cdotr)中受限制后继问题,并表明受限制后继问题相当于一个特殊情况,即限制的多个序列调整问题也能够得到解决。

0
下载
关闭预览

相关内容

【经典书】算法C语言实现,Algorithms in C. 672页pdf
专知会员服务
81+阅读 · 2020年8月13日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【LeetCode 136】 关关的刷题日记32 Single Number
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月26日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
VIP会员
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【LeetCode 136】 关关的刷题日记32 Single Number
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员