为什么我在leetcode中得到堆缓冲区溢出?

ncgqoxb0  于 2023-08-03  发布在  其他
关注(0)|答案(3)|浏览(180)

我试图解决一个返回字符串中最长回文的问题。我首先以相反的顺序复制字符串,然后尝试查找最长的子串。下面是我写的代码:

char *longestPalindrome(char *s) {
    int len = strlen(s);
    char c[len];
    for (int i = 0; i < len; i++) {
        c[i] = s[len - 1 - i];
    }
    int st = 0;
    int length = 0;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            int l = 0;
            for (int k = 0; ((i + k) < len) && ((j + k) < len); k++) {
                if (s[i + k] == c[j + k])
                    l++;
                else
                    break;
            }
            if (l > length) {
                length = l;
                st = i;
            }
        }
    }
    char *ans = (char *)calloc(length, sizeof(char));
    for (int i = 0; (i < length) && (i + st < len); i++) {
        ans[i] = s[i + st];
    }
    return ans;  
}

字符串
我不断收到此错误:

ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000033
  at pc 0x559567cee1ab bp 0x7ffdab22ea70 sp 0x7ffdab22ea60


现在,当我注解掉第三个for循环中的if-else条件时,我没有得到任何错误。为什么会发生这种情况?尽管添加了条件(i + k) < len(j + k) < len
我试着注解掉if-else条件,代码没有给出错误。

2ul0zpep

2ul0zpep1#

代码中存在多个问题:

  • 你必须为匹配分配一个额外的字节,并在块的末尾存储一个空终止符,使其成为一个正确的C字符串:
char *ans = calloc(length + 1, sizeof(char));
  for (int i = 0; i < length; i++) {
      ans[i] = s[st + i];
  }
  ans[length] = '\0';
  return ans;

字符串
请注意,您也可以使用strndup()并将整个代码块替换为

return strndup(st + i, length);


如果没有空终止符,调用代码将导致越界访问,因为它试图定位字符串的结尾,例如在打印字符串时。

  • 该算法不会在参数字符串中找到嵌入的回文,它会找到恰好在参数字符串的某处嵌入了反转版本的子字符串。例如,对于"a dog has no god",将返回"dog ",这不是回文。

以下是修改后的版本:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *longestPalindrome(const char *s) {
    size_t len = strlen(s);
    size_t st = 0;
    size_t length = 0;
    size_t i, n, k;
    for (i = 0; i + length < len; i++) {
        for (n = length + 1; i + n < len; n++) {
            for (k = 0; k < n; k++) {
                if (s[i + k] != s[i + n - 1 - k])
                    break;
            }
            if (k == n) {
                /* found a palindrome of length n */
                length = n;
                st = i;
            }
        }
    }
    return strndup(s + st, length);
}

int main(int argc, char *argv[]) {
    for (int i = 1; i < argc; i++) {
        char *p = longestPalindrome(argv[i]);
        printf("'%s' -> '%s'\n", argv[i], p);
        free(p);
    }
    return 0;
}


strdupstrndup函数很长一段时间以来一直是POSIX标准的一部分,它们最终被纳入即将到来的C23标准。如果strndup()在您的系统上不可用,可以这样写:

#include <stdlib.h>
#include <string.h>

char *strndup(const char *s, size_t n) {
    char *p = malloc(n + 1);
    if (p != NULL) {
        memcpy(p, s, n);
        p[n] = '\0';
    }
    return p;
}

idv4meu8

idv4meu82#

看起来你只需要在打印结果字符串之前终止它。将calloc(length, ...更改为calloc(length + 1, ...

lbsnaicq

lbsnaicq3#

发布的代码不会给予问题中发布的错误。在发布的代码中没有越界访问。
换句话说-错误来自一些没有发布的代码。也许/很可能是longestPalindrome的调用者使用返回的指针ans的方式导致了发布的错误。
关键在这里:
...返回字符串中最长的回文 *。
您的代码没有返回C样式字符串。分配的内存不包含字符串终止字符(NUL终止)。(注意:当前分配的内存中甚至没有空间用于终止)
所以如果caller执行如下操作:

...
char* str = longestPalindrome(someString);
if (str) puts(str);

字符串
puts调用将访问越界存储器。
解决方案:确保ans指向包含终止字符的内存。
另外,代码不处理输入为空字符串的情况。这也可能导致错误。
顺便说一句:使用char c[len];等VLA时要小心。如果输入的字符串很大,可能会导致堆栈溢出。

相关问题