Back to Search
Start Over
An efficient algorithm for the longest common palindromic subsequence problem.
- Source :
-
Theoretical Computer Science . Jun2022, Vol. 922, p475-485. 11p. - Publication Year :
- 2022
-
Abstract
- The longest common palindromic subsequence (LCPS) problem is a variant of the longest common subsequence (LCS) problem. Given two input sequences A and B , the LCPS problem is to find the common subsequence of A and B such that the answer is a palindrome with the maximal length. The LCPS problem was first proposed by Chowdhury et al. (2014) [9] , who proposed a dynamic programming algorithm with O (m 2 n 2) time, where m and n denote the lengths of A and B , respectively. This paper proposes a diagonal-based algorithm for solving the LCPS problem with O (L (m − L) R log n) time and O (R L) space, where R denotes the number of match pairs between A and B , and L denotes the LCPS length. In our algorithm, the 3-dimensional minima finding algorithm is invoked to overcome the domination problem. As experimental results show, our algorithm is efficient practically compared with some previously published algorithms. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 922
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 157328786
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.04.046