지수 시간에서 가장 긴 공통 서브 시퀀스를 찾는 방법은 무엇입니까?

Question

나는 이것을 동적 프로그래밍을 사용하여 적절한 방법으로 할 수는 있지만 지수 적 시간에 어떻게 수행하는지 알 수는 없다.

두 문자열 사이에서 가장 큰 공통 하위 시퀀스를 찾으려고합니다. 참고 : 시퀀스를 구성하는 기호가 연속 일 필요는 없으며 하위 문자열이 아닌 하위 시퀀스를 의미합니다.

Answer 1

동적 프로그래밍 코드의 테이블에있는 조회를 재귀 호출로 바꿉니다.

편집 의사에

(실제로는 거의-파이썬) : 기본적으로

def lcs(s1, s2): 
if len(s1)==0 or len(s2)==0: return 0 
if s1[0] == s2[0]: return 1 + lcs(s1[1:], s2[1:]) 
return max(lcs(s1, s2[1:]), lcs(s1[1:], s2)) 

Answer 2

당신이 경우 즉, 단지 LCS 문제의 재귀 공식을 구현 동적 프로그래밍 패러다임을 사용하지 마십시오. 지수적인 시간에 도달합니다. 이는 부분 값을 저장하지 않음으로써 부분 값을 여러 번 다시 계산하기 때문입니다.

Answer 3

길이가 n 인 a과 b의 두 개의 문자열이 있다고 가정 해 보겠습니다. 가장 긴 공통 서브 시퀀스는 문자열 b에도 존재하는 a 문자열에서 가장 긴 하위 시퀀스가 ​​될 것입니다.

따라서 a에서 가능한 모든 하위 시퀀스를 반복 할 수 있으며 b에 있습니다.

for i=n to 0 
    for all length i subsequences s of a 
     if s is a subsequence of b 
      return s 

Answer 4

문자열 A와 문자열 B. A는 재귀 알고리즘, 어쩌면 순진입니다 그러나 그것은 간단하다 :

이에 대한 높은 수준의 의사는 것 (A)의 첫 글자에서

봐 이것은 공통 순서에 있거나 그렇지 않을 것입니다. 'not'옵션을 고려할 때, 우리는 첫 번째 문자를 잘라 내고 재귀 적으로 호출합니다.

def common_subsequences(A,B, len_subsequence_so_far = 0): 
    if len(A) == 0 or len(B) == 0: 
     return 
    first_of_A = A[0] // the first letter in A. 
    A1 = A[1:] // A, but with the first letter removed 
    common_subsequences(A1,B,len_subsequence_so_far) // the first recursive call 
    if(the_first_letter_of_A_is_also_in_B): 
     Bn = ... delete from the start of B up to, and including, 
      ... the first letter which equals first_of_A 
     common_subsequences(A1,Bn, 1+len_subsequence_so_far) 

당신은 할 수 다음 '일반적인 순서입니다'옵션을 고려할 때 B에, 일부 의사를 같은 편지를 우리는 또한 그것을 잘라내 우리는 또한까지 B의 시작으로부터 트림 등 지금까지 발견 된 가장 긴 시퀀스를 기억하고 현재 함수가 이길 수 없을 때 조기 반환하여 최적화 그와 함께 시작하고 (즉, min(len(A), len(B))+len_subsequence_so_far 지금까지 발견 된 가장 긴 길이보다 작은 경우.

Answer 5

나는 우리가 을 사용할 수있는 것 같아요 동적 프로그래밍 (DP) 및 계산 가장 긴 공통 부분 시퀀스. 전체 설명은 LCS의 길이가 공통 서브가 없습니다 의미 0 일 때

     lcs("ABCD", "AFDX") 
        /     \ 
    lcs("ABC", "AFDX")     lcs("ABCD", "AFD") 
    /   \     /    \ 
lcs("AB", "AFDX") lcs("AXY", "AFD") lcs("ABC", "AFD") lcs("ABCD", "AF") 

최악의 경우는 다음과 같습니다 다음 http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

#include <iostream> 
#include <cstring> 

#define MAX1 1000 
#define MAX2 1000 

using namespace std; 


int val[MAX1][MAX2]; 

int maximum(int x, int y) { 
    if(x>=y) { 
     return x; 
    } else { 
     return y; 
    } 
} 

int longestCommonSubsequence_recur(char str1[MAX1], int i, char str2[MAX2], int j) { 

    if(i<0 || j<0) { 
     return 0; 
    } else if(val[i][j] != -1) { 
     return val[i][j]; 
    } 

    if(str1[i]==str2[j]) { 
     val[i][j] = 1 + longestCommonSubsequence_recur(str1, i-1, str2, j-1); 
    } else { 
     val[i][j] = maximum(longestCommonSubsequence_recur(str1, i, str2, j-1) , longestCommonSubsequence_recur(str1, i-1, str2, j)); 
    } 

    return val[i][j]; 
} 


int main() { 

    int length1, length2, num; 
    char str1[MAX1], str2[MAX2]; 

    cout<<"String 1 : "; 
    cin>>str1; 
    length1 = strlen(str1); 

    cout<<"String 2 : "; 
    cin>>str2; 
    length2 = strlen(str2); 


    // Initialize the Value Array by "-1" 
    for(int i=0; i<length1; i++) { 
     for(int j=0; j<length2; j++) { 
      val[i][j] = -1; 
     } 
    } 

    num = longestCommonSubsequence_recur(str1, length1-1, str2, length2-1); 

    cout<<endl<<num;  

    return 0; 
} 

Answer 6

int lcs(char[] x, int i, char[] y, int j) { 
    if (i == 0 || j == 0) return 0; 
    if (x[i - 1] == y[j - 1]) return lcs(x, i - 1, y, j - 1) + 1; 
    return Math.max(lcs(x, i, y, j - 1), lcs(x, i - 1, y, j)); 
} 

print(lcs(x, x.length, y, y.length); 

에서 찾을 수하는 부분 재귀 트리입니다.이 경우 모든 가능한 하위 시퀀스를 검사하고 O(2^n) 하위 시퀀스가 ​​있습니다.

Answer 7

지수 시간을 달성하려면 두 배열의 모든 하위 시퀀스를 생성하고 각 배열을 서로 비교하는 것으로 충분합니다. 일치하는 두 개가 일치하면 길이가 현재 최대 값보다 큰지 확인하십시오. 의사 코드는 다음과 같습니다

Generate all subsequences of `array1` and `array2`. 
for each subsequence of `array1` as s1 
    for each subsequece of `array2` as s2 
     if s1 == s2 //check char by char 
      if len(s1) > currentMax 
       currentMax = len(s1) 
for i = 0; i < 2^2; i++; 

그것은 절대적으로 최적이 아닌입니다. 시도조차하지 않습니다. 그러나 질문은 매우 비효율적 인 알고리즘에 관한 것이므로 하나를 제공했습니다.