期刊
INFORMATION PROCESSING LETTERS
卷 129, 期 -, 页码 11-15出版社
ELSEVIER
DOI: 10.1016/j.ipl.2017.08.006
关键词
Algorithms; String processing; Palindromic subsequences; Longest common subsequences; Nesting rectangles
资金
- Grants-in-Aid for Scientific Research [17H01697] Funding Source: KAKEN
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 (sigma M-2 + n) time, where n denotes the length of A and B, M denotes the number of matching positions between A and B, and a 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 sigma = o(log(2) n log log n). (C) 2017 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据