递归 strstr 函数

Question

Write the function strstr such that it would be a recursive function (not a wrapper for recursion) using the following signature.

简而言之，strstr returns substr 在 str 中首先出现的位置的索引，如果没有找到它 returns -1。更多here

这是我的尝试：

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

    if (*str == 0 || *substr == 0)//basis, if any of the strings is empty, will return -1
        return -1;
    else{
        strstr1(str + 1, substr); //forward the address of str
        if (*str == *substr)    //for each level check if the first char matches, then it should match each pair
            strstr(str + 1, substr + 1);

但是我卡住了。我意识到在递归中可能需要回溯，但我不知道如何做，也不知道如何通过所有递归级别传递索引...

有什么提示或建议吗？

Answer 1

使用以下规则：如果 substr 是空字符串，则查找 strstr 的规范以找到您应该 return 的内容。否则，如果 str 是空字符串，则 return NULL。否则，如果 strcmp (str, substr) == 0 那么 return str。否则，return strstr (str + 1, substr)。

也就是说，这是一个相当愚蠢的递归示例，因为实际上您会使用一个循环，其中只要 *str != '\0' 就将 str 增加 1。

也就是说，strstr 是一个标准库函数。如果你实现一个名为 strstr 的函数，你将有未定义的行为。如果你实现一个名为 strstr 的函数，它与标准库函数具有不同的规范，你最终会进入 DS。

Answer 2

"Real" strstr() returns 一个 char *（或 const char *）。在 C++ 标准中，有 2 个重载。为了避免链接器问题，我将 strstr() 重命名为 strstr1()。

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

int strmatch( const char *str, const char *substr)
{
    while ( '[=10=]' != (*substr) && (*str == *substr) )
    {
        substr++;
        str++;
    }
    if( '[=10=]' == *substr )
        return 0;
    else
        return -1;
}

const char * strstr1( const char *str, const char* substr)
{
    printf("strstr(%s,%s)\n", str,substr );
    if( '[=10=]' == (*str) )
        return NULL;
    if( *str == *substr )
    {
        if( 0 == strmatch( str, substr ) )
        {
            return str; // success value or something.
        }
    }
    return strstr1( str + 1, substr );
}



int main( int argc, const char * argv[] )
{
    const char * s1 = "Hello World";
    const char * ss1 = "World";

    if( NULL != strstr1( s1, ss1 ) )
    {
        printf("%s contains %s!\n", s1, ss1 );
    }
    else
    {
        printf("%s does not contain %s!\n", s1, ss1 );
    }

    const char * s2 = "Hello Universe";
    const char * ss2 = "World";

    if( NULL != strstr1( s2, ss2 ) )
    {
        printf("%s contains %s!\n", s2, ss2 );
    }
    else
    {
        printf("%s does not contain %s!\n", s2, ss2 );
    }

    const char * s3 = "Hello World World World World";
    const char * ss3 = "World";

    const char * foo = s3;
    while( NULL != foo )
    {
        foo = strstr1( foo, ss3 );
        if( NULL != foo )
        {
            puts("another match!");
            foo = foo + strlen(ss3);
        }
        else
        {
            puts("no more matches.");
        }
    }

    return 0;
}

递归 strstr 函数

Recursive strstr function

c

recursion

function