I keep getting "ERROR: AddressSanitizer: heap-buffer-overflow on address"

I keep getting "ERROR: AddressSanitizer: heap-buffer-overflow on address"

我无法找出这个错误。

问题 > 编写一个函数来查找字符串数组中最长的公共前缀字符串。如果没有公共前缀，return 一个空字符串 "".

char * longestCommonPrefix(char ** strs, int strsSize){
    int i = 1;
    int j = 0;
    int k = 1;
    int n = 0;
    
    if (strsSize == 0) return ("");
    if (strsSize == 1) return (strs[0]); 
    if (strsSize > 1 && strcmp(strs[0],"") == 0) return ("");
    
    char *s = calloc(strlen(strs[0]), sizeof(char));
    char *temp = calloc(strlen(strs[0]), sizeof(char));
    if (!s || !temp) return (0);
    
    // while (strs[0][j] != '[=10=]') {
    //     temp[j] = strs[0][j];
    //     j++;
    // }
    strcpy(temp, strs[0]);
    
    while (k < strsSize) {
        j = 0;
        n = 0;
        memset(s, 0, strlen(s));
        while (strs[i][j]){
            if (temp[j] == strs[i][j]) {
                s[n] = strs[i][j];
                n++;
            }
            else if (temp[j] != strs[i][j]){
                break;
            }
            j++;
        }
        strcpy(temp, s);
        k++;
        i++;
    }
    return (s);
}

它在我的 visual studio 上没有任何问题，但是当我将这段代码提交到 Leetcode 时，它​​总是有错误信息。我假设错误发生在第 7 行或第 8 行，因为当我隐藏这两行代码时它不会显示相同的错误。此外，当我使用 while 循环将 strs[0] 字符串复制到 temp 时，它在 Leetcode 和 visual studio 上都可以正常工作，但是当我在 Leetcode 上使用“scrcpy”函数时它不起作用，但它再次在我的 visual studio.

又是一个小问题。我使用 calloc 分配内存的原因是因为它在使用 malloc 时显示相同的错误消息“Address sani~”。 visual studio 没关系。 calloc 和 malloc 都工作正常。

我为 NULL 终止符添加了额外的内存。

char *s = malloc((strlen(strs[0]) + 1) * sizeof(char));

在我看来还不错，但它有同样的内存问题。

我尝试了很多不同的方法，但我仍然对使用 malloc 和清除字符串的方式有疑问。

int len = strlen(strs[0]);
char *temp = malloc((len+1) * sizeof(char)) 
//it still gives me a memory error.

当我用 memset 清除我的字符串时，它 return 是一个正确的输出，但是当我简单地使用 NULL 终止符清除字符串时它不是 return 正确的答案。有区别吗？

s[j] = '[=13=]';
memset(s, 0, strlen(s));

malloc和calloc的主要区别是malloc只保留内存不修改内容，而calloc保留内存而zero-initializes 每个字节。

那么，在您开始将字符串前缀复制到 s 的循环中发生的事情是您这样做的：

memset(s, 0, strlen(s));

现在，您认为您刚刚清除了字符串，但此时这是您第一次对 s 进行任何操作。因此，如果 s 与 malloc 一起分配，那么调用 strlen(s) 可以做任何事情。很可能未初始化的内存内容不会是 NUL-terminated 字符串，并且 strlen 会愉快地搜索超过该内存块的末尾并进入您的程序未请求的内存的其他部分。

这称为未定义行为。

那么，你能做些什么呢？好吧，在您尝试过的评论中：

s[0] = '[=11=]';

太棒了！但是现在字符串的每个其他字节都没有初始化。您即将遍历 strs[i] 并将内容复制到 s。问题是 afterwards 你从来没有在 NUL-terminator 中复制过，所以你又一次得到了一个 un-terminated 字符串。而且，具体来说，那个终止符应该去的地方仍然未初始化。

正如我很早就在评论中所说的那样，您需要做的就是在复制后写下终止符。您实际上并不需要 j 和 n 这两个变量，因为它们无论如何都会是相同的值。让我们使用 j。它使代码更简单。

j = 0;
while (strs[i][j] && temp[j] == strs[i][j])
{
    s[j] = strs[i][j];
    j++;
}
s[j] = '[=12=]';

就是这样。你有一个终止的字符串。您不需要 pre-initialize 它，因为无论如何您都将要覆盖该内存。重要的部分是循环之后的那一行。

现在，让我们考虑一下您在这里真正想要实现的目标。

任务是搜索数组中的所有字符串并找到最长的公共前缀。看看你的代码，它不仅做了太多的工作，实际上甚至没有完成所需的任务。提示：您从未使用过变量 k.

那么为什么不退后一步，以不同的方式思考呢？您真的需要一遍又一遍地复制前缀吗？不，你不知道。您需要做的就是查看他们有多少个相同的字符。而且，您甚至不需要检查所有字符——您只需要检查已经找到的任何最大字符数。

// Find longest common prefix
int commonPrefixLength = strlen(strs[0]);
for (int i = 1; i < strsSize; i++)
{
    int p = 0;
    while (p < commonPrefixLength && strs[i][p] == strs[0][p]) ++p;
    commonPrefixLength = p;
}

// Copy prefix to a new string
char *commonPrefix = malloc(commonPrefixLength + 1);
memcpy(commonPrefix, strs[0], commonPrefixLength);
commonPrefix[commonPrefixLength] = 0;

这就是您需要做的全部。你甚至不需要在搜索字符串时检查 NUL 终止符，因为你已经用最长的前缀 和 来限制搜索，如果你遇到 NUL-terminator 那么它将不等于您在 strs[0] 中测试的字符。不错

但是我们还有另一个问题，那就是您的函数与 return 的内容不一致。您编写了一些可能 return strs[0] 或字符串文字 "" 的特殊情况。否则它会分配新的内存和 returns 。这是一个问题，因为调用者不知道是否应该释放此内存。

所以你应该决定。选项是：

  1. 函数分配或 returns NULL -- 调用者总是负责释放内存。
  2. 函数从不分配 -- returns NULL 或修改 str[0] 和 returns that

如果您选择 2，那么您不会在循环后分配和复制内容，而只是终止字符串。但是，只有当输入数组不是字符串文字时才能这样做：

strs[0][commonPrefixLength] = '[=14=]';

所以最安全的选择可能是选项 1。但这里都有...

选项 1：

char * longestCommonPrefix(char ** strs, int strsSize)
{
    if (strsSize == 0)
        return NULL;

    int commonPrefixLength = strlen(strs[0]);
    for (int i = 1; i < strsSize; i++)
    {
        int p = 0;
        while (p < commonPrefixLength && strs[i][p] == strs[0][p]) ++p;
        commonPrefixLength = p;
    }

    char *commonPrefix = malloc(commonPrefixLength + 1);
    if (commonPrefix != NULL)
    {
        memcpy(commonPrefix, strs[0], commonPrefixLength);
        commonPrefix[commonPrefixLength] = 0;
    }
    return commonPrefix;
}

选项 2：

char * longestCommonPrefix(char ** strs, int strsSize)
{
    if (strsSize == 0)
        return NULL;

    int commonPrefixLength = strlen(strs[0]);
    for (int i = 1; i < strsSize; i++)
    {
        int p = 0;
        while (p < commonPrefixLength && strs[i][p] == strs[0][p]) ++p;
        commonPrefixLength = p;
    }

    strs[0][commonPrefixLength] = '[=16=]';
    return strs[0];
}

现场演示：https://godbolt.org/z/bebs7zz6j