Tiếp theo Palindromic phổ biến dài nhất

Question

Có bất kỳ thuật toán hiệu quả nào tính toán độ dài của Tiếp điểm Palindromic chung dài nhất của hai chuỗi đã cho không?

ví dụ:

chuỗi 1. afbcdfca

chuỗi 2. bcadfcgyfka

các LCPS 5 và LCPS chuỗi là afcfa.

Answer 1

Có.

Chỉ cần sử dụng thuật toán cho LCS cho nhiều hơn hai chuỗi.

Nếu tôi không nhầm, sau đó

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

Đó là tùy thuộc vào bạn để tìm ra chuỗi # 2 và # 4.

Cập nhật: Không, đây là một ví dụ: LCS (aba, aba, bab, bab) = ab, ba. LCS không đảm bảo rằng hậu tố sẽ là palindrome, bạn có thể cần thêm ràng buộc này. Dù sao, phương trình lặp lại cho LCS là một điểm khởi đầu tốt.

Nếu bạn triển khai LCS theo kiểu máy phát, để nó tạo ra tất cả LCS có độ dài n, sau đó là n-1, n-2, vv, bạn sẽ có thể tính toán hiệu quả một cách hiệu quả thành viên phổ biến dài nhất trong LCS- gen (string1, reverse-string1), LCS-gen (chuỗi 2, chuỗi ngược 2). Nhưng tôi chưa kiểm tra, nếu có một LCS-gen hiệu quả cao.

Answer 2

Nó giống như vấn đề này: http://code.google.com/codejam/contest/1781488/dashboard#s=p2

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

Trong đoạn mã dưới đây tôi cung cấp cho bạn một phương pháp cd (s) (trả về một dict char mà cho bạn biết nơi các char tiếp theo hoặc trước đó trong chuỗi là bằng với char đó). Sử dụng điều này để triển khai giải pháp lập trình động mà tôi cũng đã cung cấp cho bạn mã mẫu.

Với lập trình động chỉ có len (s1) * len (s1)/2 trạng thái để thứ tự (N^2) là có thể.

Ý tưởng là lấy một từ từ s1 hoặc không lấy nó. Nếu bạn lấy char off s1, bạn phải lấy nó từ phía trước và mặt sau (của cả s1 và s2). Nếu bạn không lấy nó, bạn di chuyển về phía trước 1. (điều này có nghĩa là trạng thái của s2 giữ đồng bộ với trạng thái của s1 vì bạn luôn tham lam từ bên ngoài của cả hai - vì vậy bạn chỉ lo lắng về bao nhiêu trạng thái s1 có thể có).

Mã này giúp bạn tận dụng tối đa. cd1 (char dict 1) giúp bạn tìm ký tự tiếp theo trong s1 bằng với char bạn đang ở (cả về phía trước và phía sau).

Trong phương thức resolve() đệ quy, bạn cần phải quyết định những gì start1, end1 .. vv nên. Thêm 2 với tổng số mỗi khi bạn mất một nhân vật (trừ khi start1 == END1 - sau đó thêm 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

Dưới đây là hết sức rõ ràng dòng hương của tôi bằng dòng vì đây là khá phổ biến và hầu hết những người thời gian giải thích sự năng động lập trình phần 70% và dừng lại ở các chi tiết đẫm máu.

1) Optimal sở hạ tầng: Hãy X[0..n-1] là chuỗi đầu vào có độ dài n và L(0, n-1) là chiều dài của dãy con xuôi ngược dài nhất của X[0..n-1].

Nếu ký tự cuối cùng và đầu tiên của X là cùng, sau đó L(0, n-1) = L(1, n-2) + 2. chờ đợi lý do tại sao, nếu các nhân vật thứ 2 và thứ 2 cuối cùng không phải là giống nhau, sẽ không phải là lần cuối cùng và lần đầu tiên bing cùng là vô ích. nope "subsequence" này không phải liên tục.

/* 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)); 
} 

Xem xét việc thực hiện ở trên, sau đây là cây đệ quy một phần cho chuỗi có độ dài 6 với tất cả các ký tự khác nhau.

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

Trong cây đệ quy trên một phần, L(1, 4) đang được giải quyết hai lần. Nếu chúng ta vẽ cây đệ quy hoàn chỉnh, thì chúng ta có thể thấy rằng có nhiều vấn đề con được giải quyết lặp đi lặp lại. Cũng giống như các vấn đề lập trình động (DP) điển hình khác, có thể tránh việc tính toán lại các cùng một biểu mẫu con bằng cách xây dựng một mảng tạm thời L[][] theo cách từ dưới lên.

// Trả về chiều dài của dãy con xuôi ngược dài nhất trong 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]; 
} 

vì vậy đây là giống như các chương trình không động một cách hợp lý, nó chỉ là ở đây chúng tôi lưu kết quả trong một mảng nên chúng tôi không tính toán cùng một điều hơn và hơn