stringalgorithmlcs

Longest Common Palindromic Subsequence

Is there any efficient algorithm that counts the length of Longest Common Palindromic Subsequence of two given strings?

for example:

string 1. afbcdfca

string 2. bcadfcgyfka

the LCPS is 5 and LCPS string is afcfa.

Solution

  • Yes.

    Just use an algorithm for LCS for more than two sequences.

    If I'm not mistaken, then

     LCS( afbcdfca, acfdcbfa, bcadfcgyfka, akfygcfdacb) = afcfa

    It's up to you to figure out strings #2 and #4.

    Update: No, here is a counterexample: LCS( aba, aba, bab, bab ) = ab, ba. The LCS doesn't ensure the subsequence will be a palindrome, you probably need to add this constraint. Anyway, the recurrence equation for LCS is a good starting point.

    If you implement LCS in a generator style, so that it generates all LCS of length n, then n-1, n-2 etc., then you should be able to fairly efficiently compute the longest common member in LCS-gen(string1, reverse-string1), LCS-gen(string2, reverse-string2). But I havn't checked yet, if there is a highly efficient LCS-gen.