c - C中的递归strstr函数

Question

我编写了递归 strstr 但问题是如果我有以下代码:

char *str = "Yesterday all my troubles seemed so far away";
char *subStr[6] = { "Yes", "all", "my", "see", "far", "day" };
char *res;
int i;
printf("%s\n", str);
res = str;
for (i = 0; i<6; i++)
{
    printf("%s\n", subStr[i]);
    res = recursiveStrStr(res, subStr[i]);
    if (res == 0)
    {
        printf("The specified text is not found.\n");
        break;
    }
    else
        printf("The found text: %s\n", res);
}

我的 strstr 很好地返回 str 直到 i=5 所以 substr 是“day”，左边的 str 是“far away”，它应该返回 0 - 这意味着未找到文本，但它返回 str 不明白为什么？

我的 strstr 代码(应该是递归的):

int recursiveStrStr(char * str, char *substr)
{

    if (str == NULL  )
        return 0;
    else if (strncmp(str, substr, strlen(substr)) == 0)
        return str;
    else 
        return(recursiveStrStr(str+1, substr));

}

Answer 1

也可以编写递归 strstr，而不调用除 strstr 本身之外的任何其他函数:

char *RecStrStr(const char *haystack, const char *needle)
{
    assert(haystack);
    assert(needle);

    if(*needle == 0)
        return (char *)haystack;

    if(*haystack == 0)
        return NULL;

    if(*haystack == *needle &&
        RecStrStr(haystack + 1, needle + 1) == haystack + 1)
        return (char *)haystack;

    return RecStrStr(haystack + 1, needle);
}

基本上，有两种类型的递归调用:

1. Needle 和 haystack 当前字符匹配，在这种情况下，您将推进两个指针以比较下一个字符。
2. needle 的当前字符与 haystack 的当前字符不匹配，在这种情况下，您只需前进 haystack 的位置即可。

如果到达空终止符，这是因为needle不是haystack的子字符串，因此返回NULL。

如果达到needle的空终止，这是因为haystack和needle连续匹配，并且返回指向当前haystack位置的指针。

为什么？这就是事情变得有点复杂的地方 - 为了当needle是haystack的非连续子串时不返回肯定答案，我们需要确保下一个匹配的返回值是当前跟随的指针(这是第三个 if 中的第二个条件)。

如果needle确实是haystack的子字符串，则返回值将是匹配开始的指针。