2026-07-25T23:32:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21106 2024-09-23T09:13:16Z ddc:004 open_access

On Finding Longest Palindromic Subsequences Using Longest Common Subsequences Brodal, Gerth Stølting Fagerberg, Rolf Rysgaard, Casper Moldrup Palindromic subsequence longest common subsequence dynamic programming Two standard textbook problems illustrating dynamic programming are to find the longest common subsequence (LCS) between two strings and to find the longest palindromic subsequence (LPS) of a single string. A popular claim is that the longest palindromic subsequence in a string can be computed as the longest common subsequence between the string and the reversed string. We prove that the correctness of this claim depends on how the longest common subsequence is computed. In particular, we prove that the classical dynamic programming solution by Wagner and Fischer [JACM 1974] for finding an LCS in fact does find an LPS, while a slightly different LCS backtracking strategy makes the algorithm fail to always report a palindrome. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerth Stølting Brodal and Rolf Fagerberg and Casper Moldrup Rysgaard 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.35 urn:nbn:de:0030-drops-211068 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode