leedcoed C语言 KMP算法为什么这里会溢出？

//已自行解决...但为什么nextval=(char*)malloc(sizeof(char)*(1+ndlen))才能过呀...

又是vs2019过了leedcode不过的情况（无奈

void GetNextval(char* needle, int* nextval)
{
    int i = 0, j = -1, len = strlen(needle);
    nextval[0] = -1;
    while (i < len)
    {
        if (j == -1 || needle[i] == needle[j])
        {
            i++;
            j++;
            if (needle[i] != needle[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}

int strStr(char* haystack, char* needle) {
    int hslen = strlen(haystack), ndlen = strlen(needle);
    int i = -1, j = -1;
    int* nextval = (int*)malloc(sizeof(int) * ndlen);
    GetNextval(needle, nextval);
    while (i < hslen && j < ndlen)
    {
        if (j == -1 || haystack[i] == needle[j])
        {
            i++;
            j++;
        }
        else
            j = nextval[j];
    }
    if (j == ndlen)
        return i - j;
    else
        return -1;
}

我的几个数组应该没有溢出啊，为什么会说我overrflow呢？

引用chatGPT作答，在 GetNextval 函数中，当 i 的值增加到 len 时，下一次 needle[i] 将访问 needle 数组的越界元素。具体来说，当 i 的值等于 len - 1 时，下一次循环将执行以下代码：

if (needle[i] != needle[j])
    nextval[i] = j;
else
    nextval[i] = nextval[j];

在这里，访问 needle 数组时使用了 i 的值，而此时 i 等于 len - 1，因此将访问 needle 数组的最后一个元素 needle[len - 1]，这将导致数组越界。

要解决这个问题，可以将 while 循环中的条件从 i < len 改为 i < len - 1，这样循环在 i 的值等于 len - 1 时就会结束，不会再访问 needle 数组的越界元素。修改后的 GetNextval 函数如下所示：

void GetNextval(char* needle, int* nextval)
{
    int i = 0, j = -1, len = strlen(needle);
    nextval[0] = -1;
    while (i < len - 1)
    {
        if (j == -1 || needle[i] == needle[j])
        {
            i++;
            j++;
            if (needle[i] != needle[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}

在 strStr 函数中，同样要避免访问越界的问题。在循环中，当 i 的值增加到 hslen 时，下一次访问 haystack[i] 将访问 haystack 数组的越界元素。因此，要将循环条件从 i < hslen 改为 i < hslen - ndlen + 1，这样循环就不会访问 haystack 数组的越界元素。修改后的 strStr 函数如下所示：

int strStr(char* haystack, char* needle) {
    int hslen = strlen(haystack), ndlen = strlen(needle);
    int i = 0, j = 0;
    int* nextval = (int*)malloc(sizeof(int) * ndlen);
    GetNextval(needle, nextval);
    while (i < hslen - ndlen + 1 && j < ndlen)
    {
        if (j == -1 || haystack[i] == needle[j])
        {
            i++;
            j++;
        }
        else
            j = nextval[j];
    }
    free(nextval);
    if (j == ndlen)
        return i - j;
    else
        return -1;
}

这样，就可以避免访问越界的问题了。

以下答案由GPT-3.5大模型与博主波罗歌共同编写：
您的代码中出现了一个潜在的溢出问题：在对 nextval 数组进行动态内存分配的时候，使用了 sizeof(char) * (1 + ndlen)，这意味着实际分配了一个比 ndlen 大 1 的内存空间，也就是说，nextval 数组实际上有 ndlen + 1 个元素。

在 GetNextval 函数中，nextval[0] = -1 表示占用了 nextval 数组的第一个元素，而在后续的循环过程中，i 的上限是 len，因此当 i = len 时，要访问的是 nextval[len]，但是由于 nextval 数组实际上只有 ndlen + 1 个元素，因此会出现数组下标溢出的情况。

解决这个问题可以使用如下的两种方法：

1.将 nextval 数组的动态内存分配改成 sizeof(int) * ndlen，因为 nextval 数组中存储的是整型数值。

int* nextval = (int*)malloc(sizeof(int) * ndlen);

2.在 GetNextval 函数中将循环的判断条件改成 while (i < len && j < ndlen)，这样可以保证 nextval 数组不会出现越界的问题。

void GetNextval(char* needle, int* nextval)
{
    int i = 0, j = -1, len = strlen(needle);
    nextval[0] = -1;
    while (i < len && j < len)
    {
        if (j == -1 || needle[i] == needle[j])
        {
            i++;
            j++;
            if (needle[i] != needle[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}

希望可以帮到您！
如果我的回答解决了您的问题，请采纳！

不知道你这个问题是否已经解决, 如果还没有解决的话:

以下回答来自chatgpt:
很抱歉，根据提供的参考资料，没有与问题相关的解决方案或提示。KMP算法和链表翻转问题没有直接的关联，需要更详细的描述问题和代码才能帮助解决问题。请提供更多细节和相关代码，以便更好地帮助你解决问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

leedcoed C语言 KMP算法 为什么这里会溢出？

leedcoed C语言 KMP算法为什么这里会溢出？