【字符串】找出字符串中第一个匹配的下标

找出字符串中第一个匹配项的下标

本文只是节选公众号的中的一篇，我的公众号每日都会更新，欢迎参观 公众号算法每日一更

❝

力扣链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

题目描述：

给你两个字符串 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 仅由小写英文字符组成

❞

【字符串篇】没有KMP，就像西方世界没有耶路撒冷，就像人类社会没有封建制度！

KMP

KMP算法用于处理字符串匹配问题，其中next数组是匹配精髓，其表示前缀表。

前缀表用于处理字符串匹配时从哪里开始重新匹配的问题。这里的内容比较多，强烈建议找个视频看下，我害怕误人子弟。

❝

视频推荐：https://www.youtube.com/watch?reload=9&v=GTJr8OvyEVQ&list=LLe_gEtrHWO_KN1wZOpQT4

或国内：https://www.bilibili.com/video/BV18k4y1m7Ar/?spm_id_from=333.337.search-card.all.click&vd_source=5c053d584e3eb18e7e7530f266354372

❞

• 解法：KMP匹配

// 下面的注释是假设您已学过KMP算法
int strStr(char * haystack, char * needle){
    int lenH = strlen(haystack);
    int lenN = strlen(needle);
    int next[lenN];
    next[0] = 0;
    // 模式串needle => next数组
    for(int i = 1, j = 0; i < lenN; i++){
        // 对j迭代
        while(needle[i] != needle[j] && j != 0)
            j = next[j - 1];
        if(needle[i] == needle[j])
            next[i] = ++j;
        else
            next[i] = 0;
    }
    
    // 开始匹配，i指向haystack，j指向needle（模式串）
    for(int i = 0, j = 0; i < lenH; i++){
        // 对j迭代
        while(haystack[i] != needle[j] && j != 0)
            j = next[j - 1];
        if(haystack[i] == needle[j])
            j++;
        if(j == lenN)
            return i - j + 1;
    }
    return -1;
}