最長公共迴文子序列

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

最長的迴文序列的長度，所以這就像非動態編程邏輯，它只是在這裏，我們將結果保存在一個數組，所以我們不計算一遍又一遍的同樣的事情