实现 strStr()函数

Question

int strStr(char* haystack, char* needle) {
    int i=0,j=0;
    char *ure=(char *)haystack;
    char *s1 = NULL;
    char *s2 = NULL;
    while(*ure != '\0')
    {
        s1 = ure;
        s2=(char *)needle;
        while((* s1 != '\0')&&(* s2 != '\0')&&(* s1 == * s2))
        {
            j=i;
            s1++;
            s2++;
        }
        if(* s2 == '\0')
        {
            return j;
        }
        i++;
        ure++;
    }
    return -1;

}

int strStr(char* haystack, char* needle) 
{
    int i=0,j=0;
    char *ure=(char *)haystack;
    while(*ure != '\0')
    {
        while((* haystack != '\0')&&(* needle != '\0')&&(* haystack == * needle))
        {
            j=i;
            haystack++;
            needle++;
        }
            if(* needle == '\0')
            {
                return j;
            }
        i++;
        ure++;
    }
    return -1;

}

为什么在输入haystack="hello",needle="ll";第一份代码可以正确执行，第2份就不行，第一份代码我只是将 s1 = ure;s2=(char *)needle;多赋值而已这是为什么

Answer 1

在这两个版本的 strStr 函数中，它们都是试图在字符串 haystack 中查找子串 needle。第一份代码中，在外部循环里对 s1 和 s2 分别赋值为 ure 和 needle，然后在内部循环中逐字符比较 s1 和 s2 是否相等，直到找到匹配项或者 needle 结束。这样每次外部循环开始时都会重置 s1 和 s2 指针，确保从当前 ure 位置重新开始搜索子串。

第二份代码中，虽然也是逐字符比较 haystack 和 needle，但是在内部循环结束后并没有重置 s2 指针。这就意味着，一旦在某次外部循环中未能找到完整的子串 needle，接下来的外部循环将继续从上次未完成的位置继续比较，而不是回到当前 ure 位置重新开始。

对于输入 haystack="hello" 和 needle="ll" 来说，第一份代码能够正确地在每个 ure 位置开始重新检查子串，所以在 "hel" 后面找到了 "ll" 子串。

而第二份代码在第一次未能找到 "ll"（在 "he" 之后直接跳过了 "l"）后，第二次外部循环时，haystack 指针移动到了第二个 "l"，但此时 needle 指针已经指向了 "l" 之后的空字符 \0，所以即使后面还有匹配的 "ll"，也无法找到，从而导致无法正确执行。

为了使第二份代码也能正确找到子串，需要在内层循环之前重置 haystack 指针为 ure。以下是修改后的第二份代码：

int strStr(char* haystack, char* needle) {
    int i = 0, j = 0;
    char *ure = (char *)haystack;

    while (*ure != '\0') {
        char *haystackBackup = ure; // 添加这一行，用于备份当前待查找位置的指针

        while ((*haystack != '\0') && (*needle != '\0') && (*haystack == *needle)) {
            j = i;
            haystack++;
            needle++;
        }

        // 在内层循环结束后，恢复haystack到备份的ure位置
        haystack = haystackBackup;

        if (*needle == '\0') {
            return j;
        }

        i++;
        ure++;
    }

    return -1;
}