leetcode28.实现strStr() （暴力解法&KMP算法）

题目要求实现strstr（）函数，即输入两个字符串str1和str2，找出str2在str1中出现的第一个位置，输出下标，若str1中不存在str2作为子字符串，则返回-1。函数如下：

int strStr(string haystack, string needle);

• 解法一：暴力法

这里首先想到的是使用暴力遍历：用两层for循环，比较str1中有没有str2，若有返回开始的下标，无则返回-1。代码如下：

int strStr(string haystack, string needle) {
        //总体思路是先在总串上匹配字串，不行则在总串上后移
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i + m <= n; i++) {            // 设置跳出条件需要注意
            bool flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack[i + j] != needle[j]) {   // 此处haystack[i + j]设置较为巧妙
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }

　　具体思路和需要注意的点在注释中已经写清楚。

• 解法二：KMP算法

　　KMP算法是发明这个算法的三位大佬名字首字母的缩写，没有别的特殊含义。KMP算法的功能是匹配字符串，但是时间复杂度会比我们的暴力解法低，怎么实现的呢？

　　这里先贴一个大佬的详细讲解「代码随想录」KMP算法详解 - 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com)，具体需要注意的地方我会再补充。

　　关键点：

　　①字符串前缀的定义：不包含最后一个字符的所有以第一个字符开头的连续子串。

　　对于字符串"aabaaf"，其前缀为："a","aa","aab","aaba","aabaa"。

　　同理，字符串后缀的定义与此类似：不包含第一个字符的所有以最后一个字符结尾的连续子串

　　②前缀表的作用：用来回退的，当模式串与主串不匹配的时候模式串应该从哪里开始重新匹配。如果是暴力匹配，就需要从头开始匹配了；而使用前缀表，会得到下一步匹配中，模式串应该跳到哪个位置。

　　③前缀表的定义：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀（上文链接中有详细说明，不再赘述）。

　　依然是字符串”aabaaf“，对以第一个字母开头且其长度为1的子串"a"，最长相同前后缀为0（因为”a“前后缀都为空）；对于”aa“，其最长前后缀长度为1（前缀”a“，后缀”a“）：对于”aab“，最长相同前后缀长度为0；对于”aaba“，最长相同前后缀长度为1（前缀”a“和后缀”a“）；对于”aabaa“，最长相同前后缀长度为2；对于”aabaaf“，最长相同前后缀长度为0。

　　由上一段的推理，得到一个数组[0, 1, 0, 1, 2, 0]，即为字符串”aabaaf“的前缀表。

　　④next字符串的获取：KMP算法需要使用next数组实现退回操作，此处使用前缀表统一减一得到next数组，即[-1, 0, -1, 0, 1, -1]。（不同next数组求法不同，但殊途同归，不做深究）

　　⑤在C++程序中实现next数组的获取：

void getNext(int* next, const string& s){ //传入next数组和字符串s　　
　　 //这里使用j表示后缀末尾，i表示前缀末尾
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回溯
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

　　⑥通过上一步得到的next数组来做匹配

int strStr(string haystack, string needle) {
    if (needle.size() == 0) {
        return 0;
    }
    int next[needle.size()];
    getNext(next, needle);
    int j = -1; // // 因为next数组里记录的起始位置为-1
    for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
        while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
            j = next[j]; // j 寻找之前匹配的位置
        }
        if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
            j++; // i的增加在for循环里
        }
        if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
            return (i - needle.size() + 1);
        }
    }
    return -1;
}