稀碎从零算法笔记Day12-LeetCode:找出字符串中第一个匹配项的下标

题型：字符串、字符串匹配算法

链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

来源：LeetCode

题目描述

给你两个字符串 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长！)
• haystack 和 needle 仅由小写英文字符组成

题目思路

两种思路：暴力开撕 或者 字符串匹配算法(比如KMP算法)

暴力：笔者这里开了一个新的字符串temp来存haystack的前n个字符(假设n是needle.length()-1),然后看看temp和needle是否相等：相等就return i，不相等就让 i 右移

字符串匹配算法（施工完毕！）

KMP算法：重点：算法实现构建Next数组
这里先说一下KMP算法中的next数组：其存储的是【最长相等前后缀的长度】
手写起来还是很简单的，关键是代码实现。
我的思路：双指针 i 和 j ：其中 i 指向后缀的最后一位，j 有两重含义：① j 是最长前缀的长度 ② j 指向前缀的最后一位

然后就是判断最长相等前后缀：

 

感觉讲起来会很费劲，模拟一下代码的制行过程可能更好理解 

C++代码

暴力code：

注意index越界

class Solution {
public:
    int strStr(string haystack, string needle) {
        // 暴力
        string temp;
        if(haystack.length()length())//被匹配串比匹配串短，-1
            return -1;
        else
            for(int i=0;i<=haystack.length()-needle.length();i++)
            {
                temp="";//空串
 
                for(int j=i;jlength();j++)//一次循环次数应该是匹配串的长度-1
                {
                    temp.push_back(haystack[j]);
                }
 
                if(temp==needle)
                {
                    return i;
                }
            }
        return -1;
    }
};

 KMP算法：

class Solution {
public:
    int strStr(string haystack, string needle) {
    // KMP算法
    //重点：求模式串前缀表 构建next数组
    int lenH=haystack.length(),lenN=needle.length();//文本串的长度 模式串的长度
    int j=0;//j是①前缀的最后一位  ②最长相等前后缀的长度
    vector<int> next(lenN);//next数组,长度为
    next[0]=0;
    // 构建next数组
    for(int i=1;i//i是后缀的最后一位
    {
 
        while(j>0 && needle[j] != needle[i])
        {
            j=next[j-1];//前后缀不相等，j就移动到i的前一位的next处
        }
        if(needle[i]==needle[j])
        {
            j++;
        }
        next[i]=j;//因为j是最长相等前后缀的长度
    }
    for(int i=0,j=0;i
    {
        while(haystack[i] != needle[j] && j>0)
        {
            j=next[j-1];
        }
        if(haystack[i] == needle[j])
            j++;
        if(j==lenN)//遍历完了模式串,表示haystack中有needle
            return i-lenN+1;
    }
    return -1;
    }
};

结算页面