最常见的子序列：为什么这是错的？
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内存分配失败。
这里的问题是你的表的大小。 请注意，您将空间分配为
int *X = malloc(m * sizeof(int)); int *Y = malloc(n * sizeof(int));
但是，您使用索引0 … m和0 … n，这意味着在X中需要m + 1个时隙，在Y中需要n + 1个时隙。
尝试更改此内容以阅读
int *X = malloc((m + 1) * sizeof(int)); int *Y = malloc((n + 1) * sizeof(int));
希望这可以帮助！
系列问题。 首先，正如templatetypedef所说，你的分配不足。
然后，正如稻田所说，你没有释放你的malloc内存。 如果你需要Y=X行，你需要将原始的malloc空间地址存储在另一组变量中，这样你就可以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 }
您可以使用end_position + 1和NUL字符进行字符交换，而不是将每个候选子字符串复制到新字符串。 然后，在b中查找子字符串后，将end_position+1的原始字符交换回来。这样会快得多，但实现会稍微复杂一些。
注意：我通常不会写两个答案，如果您觉得它很俗气，请随意对此进行评论并注意投票。 这个答案是一个更优化的解决方案，但我想给出一个我能想到的最直接的解决方案，然后将其放在另一个答案中，以免混淆两者。 基本上它们适用于不同的受众。
有效解决这个问题的关键是，在寻找较长的公共子串时，不要丢弃有关较短公共子串的信息。 天真地，你检查每个子串与另一个子串，但如果你知道“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更好，即使有三个嵌套for循环，但它似乎不是我能说的最好。
不过，我正在考虑这个问题。 要么找到的子串不是字符串长度的重要部分，在这种情况下优化不会做太多，但是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; }
除了templatetypedef所说的，还有一些需要考虑的事情：
- 为什么
X和Y的大小不一样？ - 你为什么要做
Y = X？ 这是指针的分配。 你是否意味着memcpy(Y, X, (n+1)*sizeof(int))？