самая длинная общая подпоследовательность: почему это неправильно?

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

Проблема здесь с размером вашей таблицы. Обратите внимание, что вы выделить пространство как

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

Однако вы используете индексы 0 ... м и 0 ... п, что означает, что имеется т + 1 слотов, необходимых в X и п + 1 слотов необходимо в Y.

Попробуйте изменить это, чтобы читать

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

Надеется, что это помогает!

Answer 2

Серия вопросов. Во-первых, как говорит templatetypedef, вы недораспределены.

Затем, как говорит падди, вы не освобождаете свою память malloc'd. Если вам нужна строка 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]; 

Но это не касается вашего нового вопроса, поэтому почему код действительно не работает?

Я признаю, что не могу следовать вашему коду (без большого изучения), но я могу предложить алгоритм, который будет работать и будет намного понятнее. Это может быть несколько pseudocode и не особенно эффективен, но получение его правильного является первым шагом. Я перечислил некоторые оптимизации позже.

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 и a NUL знак. Затем, после поиска этой подстроки в b, замените оригинальный символ на end_position+1. Это будет намного быстрее, но немного усложнит реализацию.

Answer 3

В дополнение к тому, что templatetypedef сказал, некоторые вещи, чтобы думать:

• Почему не 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 будет сравниваться с каждой буквой в B для времени выполнения A * B.

Для последовательности, в которой имеется много совпадений, но длина совпадения не является большой частью длины более короткой строки, у вас есть комбинации A * B для проверки на более короткую из двух строк (A или B), приводящий к A * B * A или A * B * B, что в основном O (n^3) для аналогичных строк длины. Я действительно думал, что оптимизация в этом решении будет лучше, чем n^3, хотя есть трижды вложенные для циклов, но, похоже, это не так хорошо, как я могу сказать.

Я думаю об этом еще немного. Либо найденные подстроки НЕ являются значительной частью длины строк, и в этом случае оптимизации не очень много, но сравнения для каждой комбинации A * B не масштабируются с помощью A или B и выпадают на константы - OR - они являются значительной долей 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; 
}