问题

我尝试解决一个返回字符串中最长回文子串的问题。
首先，我将字符串按照相反的顺序复制，然后尝试找到最长的子字符串。
以下是我编写的代码：

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条件后，代码不再报错。

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

答案1

得分: 1

只需将calloc(length, ...更改为calloc(length + 1, ...，然后在打印之前终止结果字符串。

答案2

得分: 1

已发布的代码不会导致问题中发布的错误。在已发布的代码中没有越界访问。

换句话说，错误是由一些未发布的代码引起的。也许/很可能是longestPalindrome的调用者在使用返回的指针ans时引发了发布的错误。

关键在于：

> ...返回字符串中的最长回文串。

您的代码没有返回C风格的字符串。分配的内存不包含字符串终止字符（NUL终止符）。
（注意：当前分配的内存中甚至没有足够的空间来放置终止符）

因此，如果caller像这样做：

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

puts调用将访问越界内存。

解决方案：确保ans指向包含终止字符的内存。

此外，代码没有处理输入为空字符串的情况。这也可能导致错误。

顺便说一句：要小心使用像char c[len];这样的VLA（可变长度数组）。如果输入字符串非常大，可能会导致栈溢出。

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

答案3

得分: 1

以下是翻译好的部分：

在代码中存在多个问题：

* 你必须为匹配分配一个额外的字节，并在块的末尾存储一个空终止符，使其成为一个合适的C字符串：
  ```c
    char *ans = calloc(length + 1, sizeof(char));
    for (int i = 0; i < length; i++) {
        ans[i] = s[st + i];
    }
    ans[length] = '
在代码中存在多个问题：

* 你必须为匹配分配一个额外的字节，并在块的末尾存储一个空终止符，使其成为一个合适的C字符串：
  ```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;  
';
    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) {
                /* 找到长度为 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;
}

strdup 和 strndup 函数长期以来一直是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] = '
#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;
}
';
    }
    return p;
}

<details>
<summary>英文:</summary>

There are multiple problems in the code:

* you must allocate one extra byte for the match and store a null terminator at the end of the block to make it a proper C string:

char *ans = calloc(length + 1, sizeof(char));
for (int i = 0; i < length; i++) {
    ans[i] = s[st + i];
}
ans[length] = '
char *ans = calloc(length + 1, sizeof(char));
for (int i = 0; i < length; i++) {
ans[i] = s[st + i];
}
ans[length] = '\0';
return ans;  
';
return ans;  

note that you could also use `strndup()` and replace the whole code block with

return strndup(st + i, length);

without a null terminator, the calling code will cause an out of bounds access as it tries to locate the end of the string, for example when printing it.

* The algorithm does not find embedded palindromes in the argument string, it finds substrings that happen to have a reversed version embedded somewhere in the argument string. For example for `"a dog has no god"` will return `"dog "`, which is not a palindrome.

Here is a modified version:

#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;
}

The `strdup` and `strndup` functions have been part of the POSIX Standard for a long time, and they have finally been incorporated into the upcoming C23 standard.  If `strndup()` is not available on your system, it can be written this way:

#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;
}

</details>