最长公共回文子序列

Question

是否有任何有效的算法，计数给出的字符串的两个最长公共回文子序列的长度是多少？

例如：

串1. afbcdfca

串2. bcadfcgyfka

的LCPS是5和LCPS字符串是afcfa。

Answer 1

是。

只需使用一种算法为LCS的两个以上的序列。

如果我没有记错的话

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

这是给你找出串＃2，＃4。

更新：不，这里是一个反例：LCS（aba，aba，bab，bab）= ab，ba。 LCS不能确保子序列是一个回文，你可能需要添加这个约束。无论如何，LCS的递推方程是一个很好的起点。

如果您以生成器样式实现LCS，以便生成长度为n，然后是n-1，n-2等的所有LCS，那么您应该能够相当有效地计算LCS中最长的公共成员 - gen（string1，reverse-string1），LCS-gen（string2，reverse-string2）。但我还没有检查，如果有一个高效率的LCS-gen。

Answer 2

这是相同的，因为这问题： http://code.google.com/codejam/contest/1781488/dashboard#s=p2

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

在下面的代码，我给你一盘（CD）方法（它返回一个char字典，它告诉你下一个或前一个字符在字符串中是等于那个字符）。使用它来实现一个动态编程解决方案，我也给了你示例代码。通过动态编程，只有len（s1）* len（s1）/ 2个状态，因此order（N^2）是可能的。

的想法是任取一个字符从S1或不服用。 如果将字符从s1中取出，则必须从s1和s2的前面和后面取出它。如果你不接受它，你就向前走1.（这意味着s2的状态与s1的状态保持同步，因为你总是从两者的外面贪婪地掠夺 - 所以你只会担心s1可以拥有多少个状态）。

这段代码获得了大多数的方式出现。 CD1（字符字典1）帮助您找到下一个字符S1等于你在（向前和向后）的字符。

在递归solve（）方法中，您需要确定start1，end1 .. etc应该是什么。添加2总每次取一个字符（除非启动1 == 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)) 

Answer 3

下面是一行我的万无一失演练线，因为这是相当普遍，大多数时候人们讲解动态编程部分70％，并停止在血淋淋的细节。

1）最优子： 让X[0..n-1]是长度为n并且L(0, n-1)的输入序列是X[0..n-1].

最长回文序列的长度，如果X的最后和第一字符是相同的，那么L(0, n-1) = L(1, n-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[][]来避免相同子问题 的重新计算。

//返回序列

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]; 
} 

最长的回文序列的长度，所以这就像非动态编程逻辑，它只是在这里，我们将结果保存在一个数组，所以我们不计算一遍又一遍的同样的事情