c - strstr 的实现失败，最后一个字

Question

我有以下 strstr 的实现

注意:这段代码不是我的。

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

char *fast_strstr(const char *haystack, const char *needle)
{
    if (!*needle) // Empty needle.
        return (char *) haystack;

    const char    needle_first  = *needle;

    // Runs strchr() on the first section of the haystack as it has a lower
    // algorithmic complexity for discarding the first non-matching characters.
    haystack = strchr(haystack, needle_first);
    if (!haystack) // First character of needle is not in the haystack.
        return NULL;

    // First characters of haystack and needle are the same now. Both are
    // guaranteed to be at least one character long.
    // Now computes the sum of the first needle_len characters of haystack
    // minus the sum of characters values of needle.

    const char   *i_haystack = haystack + 1,
                  *i_needle   = needle   + 1;

    unsigned int  sums_diff = *haystack;
    bool          identical = true;

    while (*i_haystack && *i_needle)
    {
        sums_diff += *i_haystack;
        sums_diff -= *i_needle;
        identical &= *i_haystack++ == *i_needle++;
    }

    // i_haystack now references the (needle_len + 1)-th character.

    if (*i_needle) // haystack is smaller than needle.
        return NULL;
    else if (identical)
        return (char *) haystack;

    size_t needle_len = i_needle - needle;
    size_t needle_len_1 = needle_len - 1;

    // Loops for the remaining of the haystack, updating the sum iteratively.
    const char *sub_start;
    for (sub_start = haystack; *i_haystack; i_haystack++)
    {
        sums_diff -= *sub_start++;
        sums_diff += *i_haystack;

        // Since the sum of the characters is already known to be equal at that
        // point, it is enough to check just needle_len-1 characters for
        // equality.
        if (
            sums_diff == 0
            && needle_first == *sub_start // Avoids some calls to memcmp.
            && memcmp(sub_start, needle, needle_len_1) == 0
        )
            return (char *) sub_start;
    }

    return NULL;
}

int main(void)
{
    char s[] = "this is a test";
    char s2[] = "test";

    if(fast_strstr(s, s2) != NULL)
        puts("YES!");
    else
        puts("NOT!");

    return 0;
}

这给出了当前条目的错误输出，其中 NOT! 而不是 YES!。这个问题只出现在最后一个词上，但奇怪的是它适用于其他字符串，知道为什么会这样吗？

Answer 1

如果 needle 的第一个 char 与 haystack 中的 char 匹配，则代码失败，但其余的则不会。
尝试 fast_strstr("zhis is a test", "test")

而不是最后一个return NULL;，代码需要在第一个匹配字母之后尝试大海捞针的其余部分。接下来是递归解决方案，但肯定可以在函数内使用循环。

return fast_strstr(haystack+1, needle);  // --> YES!
// return NULL;

某些输入的代码可能很快，但似乎是 O(n*n)