가장 긴 공통 부분 시퀀스 : 왜 이것이 잘못 되었습니까?

Question

int lcs(char * A, char * B) 
{ 
    int m = strlen(A); 
    int n = strlen(B); 
    int *X = malloc(m * sizeof(int)); 
    int *Y = malloc(n * sizeof(int)); 
    int i; 
    int j; 
    for (i = m; i >= 0; i--) 
    { 
     for (j = n; j >= 0; j--) 
     { 
      if (A[i] == '\0' || B[j] == '\0') 
       X[j] = 0; 
      else if (A[i] == B[j]) 
       X[j] = 1 + Y[j+1]; 
      else 
       X[j] = max(Y[j], X[j+1]); 
     } 
     Y = X; 
    } 
    return X[0]; 
} 

이 방법은 작동하지만 잘못된 읽기에 대해 valgrind가 큰 소리로 불평합니다. 어떻게 기억을 어지럽 혔습니까? 죄송 합니다만, 저는 항상 C 메모리 할당에 실패합니다.

Answer 1

여기의 문제는 표의 크기와 관련이 있습니다. m은 X 필요 + 1 개 슬롯 및 N + 1 개 슬롯이 있음을 의미하면 그러나

int *X = malloc(m * sizeof(int)); 
int *Y = malloc(n * sizeof(int)); 

로 공간을 할당하고, 사용자가 인덱스 0 ... m은 0을 사용 ... N 유의 필요한 Y.

이 도움이

int *X = malloc((m + 1) * sizeof(int)); 
int *Y = malloc((n + 1) * sizeof(int)); 

희망을 읽을이 변경보십시오!

Answer 2

일련의 문제. 첫째, templatetypedef가 말했듯이, 당신은 미숙 한 상태입니다.

그러면 패디가 말했듯이, 당신은 당신의 malloc 된 메모리를 자유롭게하지 못합니다. Y=X 라인이 필요하면 원래의 malloc'd 스페이스 주소를 다른 변수 세트에 저장하여 free으로 호출해야합니다.

...mallocs... 
int * original_y = Y; 
int * original_x = X; 
...body of code... 
free(original_y); 
free(original_x); 
return X[0]; 

그러나 이것은 새로운 질문을 다루지 않으므로 코드가 실제로 작동하지 않는 이유는 무엇입니까?

나는 (더 많은 연구를하지 않고) 당신의 코드를 따라갈 수 없다는 것을 인정하지만, 나는 더 잘 이해할 수있는 알고리즘을 제안 할 수있다. 이것은 다소 의사 코드 일 수 있으며 특히 효율적이지는 않지만 올바른 정보를 얻는 것이 첫 번째 단계입니다. 나중에 몇 가지 최적화를 나열했습니다. 당신이 할 수

int lcs(char * A, char * B) 
{ 
    int length_a = strlen(A); 
    int length_b = strlen(B); 


    // these hold the position in A of the longest common substring 
    int longest_found_length = 0; 

    // go through each substring of one of the strings (doesn't matter which, you could pick the shorter one if you want) 
    char * candidate_substring = malloc(sizeof(char) * length_a + 1); 
    for (int start_position = 0; start_position < length_a; start_position++) { 
    for (int end_position = start_position; end_position < length_a; end_position++) { 

     int substring_length = end_position - start_position + 1; 

     // make a null-terminated copy of the substring to look for in the other string 
     strncpy(candidate_substring, &(A[start_position]), substring_length); 
     if (strstr(B, candidate_substring) != NULL) { 
     longest_found_length = substring_length; 
     } 
    } 

    } 
    free(candidate_substring); 
    return longest_found_length; 
} 

일부 다른 최적화 :

 // if this can't be longer, then don't bother checking it. You can play games with the for loop to not have this happen, but it's more complicated. 
     if (substring_length <= longest_found_index) { 
     continue; 
     } 

및

 // there are more optimizations you could do to this, but don't check 
     // the substring if it's longer than b, since b can't contain it. 
     if (substring_length > length_b) { 
     continue; 
     } 

하고 대신 새로운 문자열로 각 후보의 문자열을 복사

if (strstr(B, candidate_substring) != NULL) { 
    longest_found_length = end_position - start_position + 1; 
    } else { 
    // if nothing contains the shorter string, then nothing can contain the longer one, so skip checking longer strings with the same starting character 
    break; // skip out of inner loop to next iteration of start_position 
    } 

, 당신은 할 수 t로 문자 교환하기 그는 end_position + 1 및 NUL 문자입니다. 그런 다음 b에서 해당 하위 문자열을 찾은 후 원래 문자 인 end_position+1을 다시 넣습니다.이 방법은 훨씬 빠르지 만 구현이 약간 복잡합니다. templatetypedef 말한 외에도

Answer 3

은 몇 가지 생각하는 약 :

• 왜 X 및 Y 같은 크기?
• 왜 Y = X을하고 있습니까? 그것은 포인터의 할당입니다. 아마도 memcpy(Y, X, (n+1)*sizeof(int))을 의미 했습니까?

Answer 4

참고 : 일반적으로 두 개의 답변을 쓰지 않으며, 끈적하다고 생각되면 자유롭게 의견을 말하고 투표하십시오.이 답변은 좀 더 최적화 된 솔루션이지만, 가장 먼저 생각한 가장 간단한 것을주고 싶었고, 두 가지를 혼동하지 않도록 다른 대답을 사용하기를 원했습니다. 기본적으로 그들은 다른 관객을위한 것입니다.

이 문제를 효율적으로 해결하는 열쇠는 더 긴 공통 부분 문자열을 찾을 때 더 짧은 공통 부분 문자열에 대한 정보를 버리지 않는 것입니다. 순진하게도 각 부분 문자열을 다른 부분과 비교하여 검사하지만 "AB"가 "ABC"와 일치하고 다음 문자가 C 인 경우 "ABC"가 "ABC"에 있는지 확인하지 않고 확인 만하면됩니다 "AB"다음의 자리는 "C"입니다.

A의 각 문자에 대해 B의 모든 문자를 검사해야하지만 더 이상 긴 하위 문자열은 검색 할 수 없으므로 B를 살펴 보는 것이 더 이상 불가능하기 때문에 검사 ​​수를 크게 제한합니다. 더 긴 매치업을 얻을 때마다 백엔드에 대한 검사가 제거됩니다. 더 이상 하위 문자열이 아니기 때문입니다.

예를 들어, A와 B가 모두 길지만 공통 문자가없는 경우 A의 각 문자는 A * B의 런타임을 위해 B의 각 문자와 비교됩니다.

일치하는 항목이 많지만 일치하는 길이가 짧은 문자열의 길이의 큰 부분이 아닌 순서의 경우 두 문자열 중 더 짧은 것에 대해 확인하는 A * B 조합이 있습니다 (A 또는 B) A * B * A 또는 A * B * B로 이어지며, 이는 비슷한 길이의 문자열에 대해 기본적으로 O (n^3) 시간입니다. 루프에 대해 트리플 중첩이 있더라도이 솔루션의 최적화가 n^3보다 좋을 것이라고 생각했지만 최대한 잘 알지 못합니다.

나는 이것에 대해 좀 더 생각하고 있습니다. 찾은 부분 문자열이 문자열의 길이의 상당 부분이 아니거나 최적화가 많지는 않지만 A * B의 각 조합에 대한 비교는 A 나 B로 확장되지 않고 상수 일 수 있습니다 - 또는 - 그들은 A와 B의 중요한 분수이며 비교되어야하는 A * B 조합에 대해 직접 분열합니다.

나는 질문 할 수 있습니다.

int lcs(char * A, char * B) 
{ 
    int length_a = strlen(A); 
    int length_b = strlen(B); 

    // these hold the position in A of the longest common substring 
    int longest_length_found = 0; 

    // for each character in one string (doesn't matter which), look for incrementally larger strings in the other 
    for (int a_index = 0; a_index < length_a - longest_length_found; a_index++) { 
    for (int b_index = 0; b_index < length_b - longest_length_found; b_index++) { 

     // offset into each string until end of string or non-matching character is found 
     for (int offset = 0; A[a_index+offset] != '\0' && B[b_index+offset] != '\0' && A[a_index+offset] == B[b_index+offset]; offset++) {   
     longest_length_found = longest_length_found > offset ? longest_length_found : offset; 
     } 
    } 
    } 
    return longest_found_length; 
}