Computing a Longest Common Palindromic Subsequence

DOI10.1007/978-3-642-35926-2_24MaRDI QIDQ2876577zbMATH OpenOpenAlexFDO

Authors Shihabur Rahman Chowdhury, Md. Mahbubul Hasan, Sumaiya Iqbal, M. Sohel Rahman

Publication date 19 August 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.5296

zbMATH Keywords

dynamic programminglongest common subsequencerange querypalindromes

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: The {em longest common subsequence (LCS)} problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The {em 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.

Recommendations

• Computing a longest common palindromic subsequence
• On finding a longest common palindromic subsequence
• An efficient algorithm for the longest common palindromic subsequence problem
• Computing longest (common) Lyndon subsequences
• Anytime algorithms for the longest common palindromic subsequence problem
• Computing longest common square subsequences
• Computing Longest Common Substring and All Palindromes from Compressed Strings
• Palindromic subsequence automata and longest common palindromic subsequence
• Computing the longest common almost-increasing subsequence
• Longest common subsequences

Cited in

(8)

• Longest substring palindrome after edit
• Longest common rollercoasters
• Computing longest palindromic substring after single-character or block-wise edits
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Anytime algorithms for the longest common palindromic subsequence problem
• On finding longest palindromic subsequences using longest common subsequences
• On finding a longest common palindromic subsequence
• Computing a longest common palindromic subsequence

This page was built for publication: Computing a Longest Common Palindromic Subsequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2876577)