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 return str 很好，直到达到 i=5 所以 substr 是 "day"，剩下的 str 是 "far away"，它应该是 return 0 - 这意味着找不到文本，但它 returns 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

我猜应该是(*str == NULL)？

Answer 2

您需要 returning "not found" 的另一个子句。

if ( *str == '[=10=]' )
   return NULL;

否则，您将一直递增 str，直到访问越界内存。

此外，我会将函数的 return 类型更改为 char*。

char* recursiveStrStr(char * str, char *substr)
{
   if (str == NULL  )
      return NULL;

   if ( *str == '[=11=]' )
      return NULL;

   if (strncmp(str, substr, strlen(substr)) == 0)
      return str;

   return(recursiveStrStr(str+1, substr));
}

Answer 3

也可以编写递归的 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);
}

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

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

如果到达空终止，那是因为 needle 不是 haystack 的子串，而 NULL 是 returned。

如果到达needle的空终止，那是因为haystack和needle连续匹配，指向当前haystack位置的指针是returned。

为什么？这是事情变得有点复杂的地方——当 needle 是 haystack 的 non-consecutive 子串时，为了不 return 一个肯定的答案，我们需要确保 return 的值下一个匹配项是当前跟随项之后的指针（这是第三个 if 中的第二个条件）。

如果 needle 确实是 haystack 的子串，return 值将是匹配开始的指针。

c中的递归strstr函数

recursive strstr function in c

c

string

recursion

strstr