⭐每天一道leetcode：28.找出字符串中第一个匹配项的下标（简单；暴力解；KMP算法，有难度）

⭐今日份题目

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例1

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例2

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示

• 1 <= haystack.length, needle.length <= 104

• haystack 和 needle 仅由小写英文字符组成

  ⭐题目思路

  还是先提取一下题目特征点：

  • 完全匹配（与needle相等的部分）

  • 第一个匹配项

  • 返回下标

    😭先说说我刚开始的错误思路：

    我想的是从头到尾遍历，然后找到最长匹配子串长度，如果和needle的长度相等，那么就是找到了，其中，只要有一个位置不匹配，那么就将匹配子串长度设为0。但我忽略了一个问题，如haystack=mississippi和needle=issip，从第二个字母开始匹配，匹配到issis时发现不是，长度置为0，但是其中包含了needle的is部分，那么长度应该为2且下一个字母应该与needle的第三个字母判断是否相等，所以就出错了。

    🍟暴力求解

    接下来说说暴力求解的方法：

    暴力求解的思路就是生成haystack中所有长度与needle相同的子串，然后找到第一个匹配项，返回其下标。

    ⭐暴力求解代码

    class Solution 
    {
    public:
        int strStr(string haystack, string needle) 
        {
            int n=haystack.size(), m=needle.size();
            for (int i=0;i+m<=n;i++) //遍历所有子串的开头所在的位置
            {
                int flag=1;
                for(int j=0;j 
    暴力求解提交结果
     
     
    🌮KMP算法
     
    Knuth-Morris-Pratt 算法的核心为前缀函数，记作 π(i)，其定义如下：
     
    对于长度为 m 的字符串 s，其前缀函数 π(i)(0≤i 
    举例说明：字符串aabaaab的前缀函数值依次为0，1，0，1，2，2，3。
     
    π(0)=0，因为 a 没有真前缀和真后缀，根据规定为 0（可以发现对于任意字符串 π(0)=0 必定成立）；
    ​
    π(1)=1，因为 aa 最长的一对相等的真前后缀为 a，长度为 1；
    ​
    π(2)=0，因为 aab 没有对应真前缀和真后缀，根据规定为 0；
    ​
    π(3)=1，因为 aaba 最长的一对相等的真前后缀为 a，长度为 1；
    ​
    π(4)=2，因为 aabaa 最长的一对相等的真前后缀为 aa，长度为 2；
    ​
    π(5)=2，因为 aabaaa 最长的一对相等的真前后缀为 aa，长度为 2；
    ​
    π(6)=3，因为 aabaaab 最长的一对相等的真前后缀为 aab，长度为 3。
     
    有了前缀函数，我们就可以快速地计算出模式串在主串中的每一次出现。
     
    （KMP算法解析来自leetcode官方，更多解析欢迎到leetcode官网进行查询）
     
    本题解法：
     
    记字符串 haystack 的长度为 n，字符串 needle 的长度为 m。
     
    我们记字符串 str=needle+#+haystack，即将字符串 needle 和 haystack 进行拼接，并用不存在于两串中的特殊字符 # 将两串隔开，然后我们对字符串 str 求前缀函数。
     
    因为特殊字符 #\ 的存在，字符串 str 中 haystack 部分的前缀函数所对应的真前缀必定落在字符串 needle 部分，真后缀必定落在字符串 haystack 部分。当 haystack 部分的前缀函数值为 m 时，我们就找到了一次字符串 needle 在字符串 haystack 中的出现（因为此时真前缀恰为字符串 needle）。
     
    实现时，我们可以进行一定的优化，包括：
     
     
    为了节约空间，我们无需真正地创建str，只需顺序遍历字符串needle、#和haystack即可
     
     
    无需保存所有前缀函数的结果，只需要保存字符串needle部分的前缀函数即可（#的前缀函数必定为0，这样我们计算 π(i) 时，j=π(π(π(…)−1)−1) 的所有的取值中仅有 π(i−1) 的下标可能大于等于 m。我们只需要保存前一个位置的前缀函数，其它的 j 的取值将全部为字符串 needle 部分的前缀函数）
     
     
    无需特别处理特殊字符 #\，只需要注意处理字符串 haystack 的第一个位置对应的前缀函数时，直接设定 j 的初值为 0 即可
     
    这样我们可以将代码实现分为两部分：
     
     
    第一部分是求 needle 部分的前缀函数，我们需要保留这部分的前缀函数值。
     
     
    第二部分是求 haystack 部分的前缀函数，我们无需保留这部分的前缀函数值，只需要用一个变量记录上一个位置的前缀函数值即可。当某个位置的前缀函数值等于 m 时，说明我们就找到了一次字符串 needle 在字符串 haystack 中的出现（因为此时真前缀恰为字符串 needle，真后缀为以当前位置为结束位置的字符串 haystack 的子串），我们计算出起始位置，将其返回即可。
     
    KMP算法代码
     
    class Solution 
    {
    public:
        int strStr(string haystack, string needle) 
        {
            int n=haystack.size(),m=needle.size();
            if(m==0) return 0;
            vector pi(m);
            for(int i=1,j=0;i0&&needle[i]!=needle[j]) 
                {
                    j=pi[j-1];
                }
                if(needle[i]==needle[j]) j++;
                pi[i]=j;
            }
            for(int i=0,j=0;i0&&haystack[i]!=needle[j]) 
                {
                    j=pi[j-1];
                }
                if (haystack[i]==needle[j]) j++;
                if (j==m) 
                {
                    return i-m+1;
                }
            }
            return -1;
        }
    };
     
    这个算法有难度，欢迎大佬们评论区留言⭐~
     
    KMP算法提交结果
     
     
    理论上KMP算法的时间复杂度比暴力求解小，内存消耗比暴力求解大，但可能是因为测评数据或者其他原因，导致提交结果如上两图所示。
     
    欢迎大家提供更高效的代码，如果过后有更优化的思路我还会继续更新的，大家评论区见！
     
    点赞收藏不迷路⭐~