A hardness result and new algorithm for the longest common palindromic subsequence problem

摘要

AbstractThe 2-LCPS problem, first introduced by Chowdhury et al. (2014) , asks one to compute (the length of) a longest common palindromic subsequence between two given stringsAandB. We show that the 2-LCPS problem is at least as hard as the well-studied longest common subsequence problem for four strings. Then, we present a new algorithm which solves the 2-LCPS problem inO(σM2+n)time, wherendenotes the length ofAandB,Mdenotes the number of matching positions betweenAandB, andσdenotes the number of distinct characters occurring in bothAandB. Our new algorithm is faster than Chowdhury et al.'s sparse algorithm whenσ=o(log2⁡nlog⁡log⁡n).Highlights•The 2-LCPS problem is to compute a longest palindromic common subsequence between two strings.•We show that the 2-LCPS problem is at least as hard as the longest common subsequence problem for four strings.•We present a new efficient algorithm which solves the 2-LCPS problem.