Geek asks and answers

The longest common palindromic subsequence

Is there an efficient algorithm that calculates the length of the longest common palindromic subsequence of two given lines?

eg:

line 1. afbcdfca

line 2. bcadfcgyfka

LCPS is 5, and the string LCPS is afcfa.

+5
source share
3 answers

Yes.

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

If I am not mistaken, then

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

You have to find out lines No. 2 and No. 4.

Update : No, here is a counterexample: LCS (aba, aba, bab, bab) = ab, ba. LCS does not guarantee that the subsequence will be a palindrome; you probably need to add this restriction. In any case, the recursive equation for LCS is a good starting point.

LCS , LCS n, n-1, n-2 .., LCS-gen (string1, reverse-string1), LCS-gen (2, 2). , LCS-gen.

+5

, , 70% gory.

1) : X[0..n-1] - n L(0, n-1) - X[0..n-1].

X , L(0, n-1) = L(1, n-2) + 2. , , 2- 2- , . "" .

/* Driver program to test above functions */
int main()
{
    char seq[] = "panamamanap";
    int n = strlen(seq);
    printf ("The lnegth of the LPS is %d", lps(seq, 0, n-1));
    getchar();
    return 0;
}

int lps(char *seq, int i, int j)
{   
    // Base Case 1: If there is only 1 character   
    if (i == j)     
        return 1;    

    // Base Case 2: If there are only 2 characters and both are same   
    if (seq[i] == seq[j] && i + 1 == j)     
        return 2;    

    // If the first and last characters match   
    if (seq[i] == seq[j])      
        return lps (seq, i+1, j-1) + 2;    

    // If the first and last characters do not match   
    else return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}

, 6 .

               L(0, 5)
             /        \ 
            /          \  
        L(1,5)          L(0,4)
       /    \            /    \
      /      \          /      \
  L(2,5)    L(1,4)  L(1,4)  L(0,3)

L(1, 4) . , , , . (DP), , L[][] .

// seq

int lps(char *str)
{
   int n = strlen(str);
   int i, j, cl;
   int L[n][n];  // Create a table to store results of subproblems


   // Strings of length 1 are palindrome of length 1
   for (i = 0; i < n; i++)
      L[i][i] = 1;

    for (cl=2; cl<=n; cl++)                              //again this is the length of chain we are considering
    {
        for (i=0; i<n-cl+1; i++)                         //start at i
        {
            j = i+cl-1;                                  //end at j
            if (str[i] == str[j] && cl == 2)             //if only 2 characters and they are the same then set L[i][j] = 2
               L[i][j] = 2;
            else if (str[i] == str[j])                   //if greater than length 2 and first and last characters match, add 2 to the calculated value of the center stripped of both ends
               L[i][j] = L[i+1][j-1] + 2;
            else
               L[i][j] = max(L[i][j-1], L[i+1][j]);      //if not match, then take max of 2 possibilities
        }
    }

    return L[0][n-1];
}

, ,

+2

, : http://code.google.com/codejam/contest/1781488/dashboard#s=p2

http://code.google.com/codejam/contest/1781488/dashboard#s=a&a=2

cd (s) ( char dict, , char char). , .

len (s1) * len (s1)/2, (N ^ 2).

, char s1, . char off s1, ( s1, s2). , 1. ( , s2 s1, - , s1 ).

. cd1 (char dict 1) s1, char, ( , ).

() , start1, end1.. .. 2 , ( start1 == end1 - 1)

s1 = "afbcdfca"
s2 = "bcadfcgyfka"

def cd(s):
    """returns dictionary d where d[i] = j where j is the next occurrence of character i"""
    char_dict = {}
    last_pos = {}
    for i, char in enumerate(s):
        if char in char_dict:
            _, forward, backward = char_dict[char]
            pos = last_pos[char]
            forward[pos] = i
            backward[i] = pos
            last_pos[char] = i
        else:
            first, forward, backward = i, {}, {}
            char_dict[char] = (first, forward, backward)
            last_pos[char] = i
    return char_dict

print cd(s1)
"""{'a': ({0: 7}, {7: 0}), 'c': ({3: 6}, {6: 3}), 'b': ({}, {}), 'd': ({}, {}), 'f': ({1: 5}, {5: 1})}"""

cd1, cd2 = cd(s1), cd(s2)

cache = {}
def solve(start1, end1, start2, end2):
    state = (start1, end1)
    answer = cache.get(state, None)
    if answer:
        return answer

    if start1 < end1:
        return 0
    c1s, c1e = s1[start1], s1[end1]
    c2s, c2e = s2[start2], s2[end2]

    #if any of c1s, c1e, c2s, c2e are equal and you don't take, you must
    #skip over those characters too:
    dont_take_end1 = solve(start1, end1 - 1, start2, end2)

    do_take_end1 = 2
    if do_take_end1:
        end1_char = s1[end1]
        #start1 = next character along from start1 that equals end1_char
        #end1 = next char before end1 that equals end1_char
        #end2 = next char before end2 that..
        #start2 = next char after .. that ..
        do_take_end1 += solve(start1, end1, start2, end2)


    answer = cache[state] = max(dont_take_end1, do_take_end1)
    return answer

print solve(0, len(s1), 0, len(s2))
0

More articles:


All Articles