کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950793 | 1441033 | 2018 | 5 صفحه PDF | دانلود رایگان |
- 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.
The 2-LCPS problem, first introduced by Chowdhury et al. (2014) [17], asks one to compute (the length of) a longest common palindromic subsequence between two given strings A and B. 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 in O(ÏM2+n) time, where n denotes the length of A and B, M denotes the number of matching positions between A and B, and Ï denotes the number of distinct characters occurring in both A and B. Our new algorithm is faster than Chowdhury et al.'s sparse algorithm when Ï=o(log2â¡nlogâ¡logâ¡n).
Journal: Information Processing Letters - Volume 129, January 2018, Pages 11-15