最长公共子：为什么这是错的？ [英] longest common subsequence: why is this wrong?

问题描述

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内存分配失败。

This works, but valgrind complains loudly about invalid reads. How was I messing up the memory? Sorry, I always fail at C memory allocation.

推荐答案

这里的问题是你的表的大小。请注意，你分配空间

The issue here is with the size of your table. Note that you're allocating space as

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

但是，使用的是标0 ...米和0 ... N，这意味着有m + x中必要时隙1和n + 1时隙必要Y中。

However, you are using indices 0 ... m and 0 ... n, which means that there are m + 1 slots necessary in X and n + 1 slots necessary in Y.

尝试改变这一阅读

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

希望这有助于！

Hope this helps!

这篇关于最长公共子：为什么这是错的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！