Computing a Longest Common Palindromic Subsequence

Computing a Longest Common Palindromic Subsequence
复制标题

计算最长公共回文子序列

DOI：
10.3233/fi-2014-974
复制
发表时间：
2011
期刊：
ArXiv
影响因子：
--
通讯作者：
Mohammad Sohel Rahman
Mohammad Sohel Rahman
中科院分区：
--
文献类型：
--
作者：
S. R. Chowdhury;Md. Mahbubul Hasan;S. Iqbal;Mohammad Sohel Rahman

文献摘要

被引文献

相似文献

最长公共子序列（LCS）问题是计算机科学中一个经典且被广泛研究的问题。回文是一个字符串，它向前读和向后读是一样的。最长公共回文子序列（LCPS）问题是经典LCS问题的一个有趣的变体，它找到两个给定字符串之间的最长公共子序列，使得计算的子序列也是一个回文序列。本文研究了LCPS问题，并给出了求解该问题的有效算法。据我们所知，这是第一次尝试研究和解决这个有趣的问题。
The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science. Palindrome is a string, which reads the same forward as it does backward. The longest common palindromic subsequence (LCPS) problem is an interesting variant of the classic LCS problem which finds the longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give efficient algorithms to solve this problem. To the best of our knowledge, this is the first attempt to study and solve this interesting problem.