一、题目

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明: 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。


二、解决方法

方法一:暴力搜索

1. 代码

废话不多说,先上代码。
最初的实现(通过):

int strStr(char* haystack, char* needle) {
    char* phk = haystack;
    char* pne = needle;
    int index = 0;
    int offset = 0;

    if (*pne == '\0')
        return 0;
    while (*phk != '\0')
    {
        if (*phk != *pne)
        {
            phk++;
            index++;
        }
        else // the cur two pointer's value is equal
        {
            phk++;
            index++;
            pne++;
            offset++;
            if (*pne == '\0' && *phk == '\0')
                return 0;
            while (*pne != '\0' && *phk != '\0')
            {
                if (*pne != *phk)
                {
                    phk++;
                    index++;
                    phk -= offset;
                    index -= offset;
                    pne -= offset;
                    offset -= offset;
                    break;
                }
                else
                {
                    pne++;
                    offset++;
                    phk++;
                    index++;
                }
                if (strlen(pne) > strlen(phk))
                    return -1;
            }
            if (*pne == '\0')
            {
                if (*phk == '\0')
                    return index - offset;
                else
                    break;
            }
        }
    }
    if (index == strlen(haystack))
        return -1;
    return index - offset;
}

执行用时图如下:

2. 思路

设置两个指针分别指向两个字符串头部,然后从字符串 haystack 头部往后遍历,去寻找其中与字符串 needle 相同的子串。这个遍历的过程中最要紧的是要注意回溯,例如对于字符串
haystack[] = "aaaba",needle[] = "aab",当两个指针都指到字符串中第三个字符时,此时字符a不等于字符b,这时我们不能把指向 haystack 的指针往后移,而是应该将指针回溯到第二个字符,再重新开始比较。由于 offset 纪录了当前字符串 needle 已经匹配了的字符的个数,即偏移量,因此需将字符串 haystack 的指针 phk 后移 offset 个间隔,这样便完成了回溯。
实现回溯的代码如下:

if (*pne != *phk)
{
    phk++;
    index++;                    
    phk -= offset;                    
    index -= offset;
    pne -= offset;
    offset -= offset;
    break;
}

3. 改进

逐个遍历字符串 haystack 前 strlen(haystack) - strlen(needle) 个字符,查找从当前字符开始长度为 strlen(needle) 的子串是否和字符串 needle 相同,如果相同,返回当前字符下标,反之则继续遍历,若没找到则返回 -1。
代码如下

int strStr(char* haystack, char* needle) {
    int M = strlen(haystack);
    int N = strlen(needle);
    for (int i = 0; i <= M - N; i++)
    {
        int j;
        for (j = 0; j < N; j++)
        {
            if (needle[j] != haystack[i + j])
                break;
        }
        if (j == N)
            return i;
    }
    return -1;
}

代码执行用时图如下所示:

什么?0ms,已经战胜100%的c提交纪录!是的,你没看错,就是100%。一开始我是不相信的,因为这个方法它是暴力搜索呀,但是,我真的提交了好几次,结果都是100%(不信你可以自己试试)。改进后的方法其实本质上和前面是一样的,都是暴力搜索,但是它却比前面的方法暴力搜索的“更聪明”,为什么这么说呢?因为它没有回溯!是的,没有回溯。仅仅因为避免了回溯就将算法的效率提升了许多。其实按照生活常识我们也能理解,比如同样的一段路程,旅行者两次都采用步行的方式,但是第一次它因为迷路所以很多时候不得不重新回到原来走过的地方,而第二次他变聪明了,他直接打开手机的GPS导航,按照给定路线一次就走到终点。虽然都是步行,但是二次花费的时间显然第二次会比第一次少很多。

改进后算法的时间复杂度分析:两个 for 循环,所以时间复杂度不难算出是 O(MN)O(MN)

看到这里,大家可能以为就要结尾了……
不,离结尾还有很长一段距离,请大家耐心看下去。

学过数据结构的同仁们可能没人会不知道赫赫有名的 KMP 算法了。是的,这是一道字符串匹配问题,我们当然不能忘记 KMP。可能有同学要问了,我们已经有了“战胜100%纪录”的方法,为什么还要管它喵的 KMP?难道 KMP 还能再提高?是的,KMP 它不可能再提高了,再高也还是100%,但是对于某些情况,KMP 算法仍然可以秒杀改进后的暴力搜索法。例如:对于字符串 txt = "aaaaaaab",pat = "aaab",碰到这种字符串 haystack 中重复的字符比较多的情况,改进后的暴力搜索法就显得很笨。
说明:此图片以及接下来的两张图片均转载自微信公众号labuladong
而 KMP 碰到这种情况是怎么处理的呢?请看下图:

仔细一看我们就会发现不一样。很明显,pat 中根本没有字符 c,根本没必要回退指针 i,暴力解法明显多做了很多不必要的操作。KMP 算法的不同之处在于,它会花费空间来记录一些信息,在上述情况中就会显得很聪明。再比如类似的 txt = "aaaaaaab" pat = "aaab",暴力解法还会和上面那个例子一样蠢蠢地回退指针 i,而 KMP 算法又会耍聪明:

因为 KMP 算法知道字符 b 之前的字符 a 都是匹配的,所以每次只需要比较字符 b 是否被匹配就行了。这就是KMP算法真的魅力所在,KMP绝对不存在回溯的可能。
打个比方:前面改进的暴力搜索法虽然有手机GPS导航,但旅行者还是免不了会不停的看手机导航信息,以免走错,这就是所谓了“走一步看一步”,而有了KMP,你的大脑就像信鸽的脑子一样(虽然没有那么小,但同样有辨识方向的能力),可以毫不思索的直奔目的地。
PS:这样说,暴力搜索法并不是最优的方法,但是其执行用时却是0ms,这引起了我的注意,于是我想有没有可能是LeetCode的代码测试器的问题呢?于是我尝试隔了一段时间后再次重新提交了解答(代码原封不动),结果得到执行用时图:

对了嘛,这执行用时才算合理。于是我积极投入到采用 KMP 来解决此问题的行动中,让我们一起来看看 KMP 算法的效率吧!


方法二:KMP算法

代码实现:

void getNextVal(char* p, int* next)
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        // p[k]表示前缀,p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++j;
            ++k;
            // 较之前next数组求法,改动在下面4行
            if (p[j] != p[k])
            {
                next[j] = k;
            }
            else
            {
                next[j] = next[k];
            }
        }
        else
        {
            k = next[k];
        }
    }
}

int kmpSearch(char* s, char* p)
{
    int i = 0;
    int j = 0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    int* next = (int*)malloc(sizeof(int) * (pLen + 1));
    getNextVal(p, next);
    while (i < sLen && j < pLen)
    {
        // ①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++
        if (j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            // ②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
            // next[j]即为j所对应的next值
            j = next[j];
        }
    }
    if (j == pLen)
    {
        free(next);
        return i - j;
    }
    else
    {
        free(next);
        return -1;
    }
}
int strStr(char* haystack, char* needle) {
    if (needle == NULL)
        return 0;
    return kmpSearch(haystack, needle);
}

代码执行用时图如下,0ms妥妥的: