1.题目描述

实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
示例1：

输入：haystack = “hello”, needle = “ll”
输出：2

示例2：

输入：haystack = “aaaaa”, needle = “bba”
输出：-1

示例3：

输入：haystack = “”, needle = “”
输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr

2.题目分析

2.1 库函数

因为string自带了字符串查找函数find，所以我们可以直接调用。形式如下

haystack.find(needle);

2.2 穷举

也就是老老实实逐个字符进行比较，以长字符串haystack为外层循环，needle字符串为内层循环，在haystack的每个位置查看是否此位置开始的子串等于needle。如果等于则返回当前位置，否则继续遍历，直到未找到退出循环。

2.3 kmp算法

2.3.1 KMP算法介绍

首先，对于kmp算法的描述我在网上查找了一些，大多都比较繁琐，个人认为这一篇文章写得很清晰明了，下面贴出链接

https://blog.sengxian.com/algorithms/kmp

虽然上面的文章已经讲得很清楚了，但是为了自我巩固还是在做一个小总结。

跟其他大多数算法一样，kmp算法也是在穷举法的基础上进行优化的出来的，它与动态规划的思想如出一辙，都是尽可能的减少重复的求值。我们可以得出穷举法的复杂度达到O(MN)，也算是n²级别的算法复杂度，这主要的原因就是每次当子串不匹配时我们都要对子串进行从头开始匹配，这就浪费了一些时间。有人就想到运用子串的规律来减少匹配的回退步骤。

还是以经典的字符串匹配例子来做一个假设，假设要在字符串str1=abaacaba中查找子串str2=ababa,我们不可避免地会遇到下面这种情况
在这里插入图片描述
按照穷举的思路，此时匹配失败，我们要同时对长串指针i和子串指针j进行回退，也就是说我们此时会回退到下面的这种状态，此时重新对i=2和j=1进行比较。反反复复直到匹配成功。

过程确实很耗时，那么如何利用子串的规律进行减少回退呢？我们这里回忆一下前缀和后缀两个概念，对于字符串aba，它的前缀就有a，ab，后缀就有b,ba。我们是不是突然有一点思路了，没错，就是利用前后缀相等的情况进行字符串指针回退的步数减少。

前缀是指除最后一个字符以外的，字符串的所有头部子串
后缀是指除最前面一个字符以外的，字符串的所有尾部子串

我们来看上面提到的匹配状态
在这里插入图片描述
我们观察这个匹配状态，发现对于其前面的已匹配成功字符串“aba”，有着相同的长度为1的前缀和后缀“a”，此时我们如果在更新两个字符串的指针位置时候利用这一规律进行如下的更新，我们就会发现我们减少了很多重循环回退。因为此时不匹配的位置之前的已经成功匹配，所以用前缀来代替后缀也是一样匹配的。
在这里插入图片描述重复此类步骤，它相比于穷举的优势就会显示出来。所以我们在进行正式字符串匹配的时候就会记录下每个位置的最长相等前缀后缀的长度用作回退，这样不仅长串指针不用回退，而且子串指针的回退会是最短的。所以可以达到O(M+N)的时间复杂度。

2.3.2 next数组求值

所以对于KMP算法的核心问题就是如何求这样的一个记录数组。KMP中将此数组命名为next数组，其每个位置的值表示本位置不匹配时子串应该回退到哪个位置。如果求出来了位置k的next数组值，那么我们用数学只是列出等式就是0~next[k]的字符串等于k-next[k]-1~k-1。有如下图示
在这里插入图片描述

我们在手动计算时可以根据列举前后缀的值和长度很清晰的写出next数组的值，但是在计算机计算时这样就显得有些冗余了，我们依旧以“ababa”为例来解释求next数组的原理。因为对于第一个元素来说不匹配的话此时不能回退，只能是长串位置移动，所以首先定义next[0]=0;我们对于next数组的求值中其下标代表的是子串的长度，所以我们很容易可以联想到next[j]和next[j+1]的前后缀是具有十分密切的联系的。所以我们考虑能否使用next[j]的值求出next[j+1]。

首先我们定义字符串s的两个指针j和i，它们分别指向前缀和后缀的末尾位置。前缀的末尾还意味着最长相等前后缀的长度。也就是说j的值其实就是next[i]。

当s[i]==s[j+1]，这就说明前i个字符0~j,j+1字符和后面的 i-j-1~i-1,i匹配中相比于前一个状态的最长前后缀长度加了1,那么就有next[j+1]=next[j]+1
当s[i] != s[j+1]，此时前缀后缀的末尾不相同，所以最长相等前后缀不会比前一状态的更长，所以要找更小的前后缀长度。这个寻找的过程也会根据next数组进行回退寻找。
- 在这个过程中，就要找j+1前一个元素在next数组中的值来替换最长相等前后缀的长度，也就是j=next[j]，直到满足前缀和后缀的最后一个字符相同。
- 上面进行j=next[j]的原因是也将这一步看作了字符串匹配，如果匹配不成功就利用该next数组进行回退。只不过这次的字符串匹配变成了自身与自身的匹配。具体可以看这篇文章的解释了解。

3.题目解答

3.1 调用库方法

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

3.2 暴力解法

class Solution {
public:
    int strStr(string haystack, string needle) {
        int len1=haystack.size(),len2 = needle.size();
        //从前到后遍历haystack字符串进行判断
        for(int i=0;i+len2<=len1;i++){
            //标记本次位置i是否成功匹配
            bool flag = true;
            //基于当前位置i开始的len2个字符串和needle作比较
            for(int j=0;j<len2;j++){
                if(haystack[i+j]!=needle[j]){
                    flag = false;
                    break;
                }
            }
            //如果本次匹配成功则返回i，否则继续循环
            if(flag){
                    return i;
            }
        }
        //匹配失败
        return -1;
    }
};

3.3 kmp算法

class Solution {
public:
    void getNext(int *next,const string &s){
        //j用来记录之前
        int j=0;
        next[0]=0;
        for(int i=1;i<s.size();i++){
            //当前字符不匹配则寻找更小的最大相等前后缀长度
            //直到遇到和当前的字符i相等的第next[j-1]个字符
            while(j>0 && s[i]!=s[j]){
                j=next[j-1];
            }
            //当前字符匹配则最大相等前后缀长度增长1单位
            if(s[i]==s[j]){
                j++;
            }
            //更新当前位置前的最大相等前后缀长度
            next[i]=j;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0)    return 0;
        int len1 = haystack.size(),len2 = needle.size();
        int next[len2];
        getNext(next,needle);
        int j=0;
        for(int i=0;i<len1;i++){
            //当前字符不匹配则根据数组回退
            while(j && haystack[i]!=needle[j]){
                j=next[j-1];
            }
            //相等则同时右移
            if(haystack[i]==needle[j]){
                j++;
            }
            //匹配完成退出
            if(j==len2) return i-len2+1;
        }
        return -1;
    }
};