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

描述

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：

1. 初始化
2. 处理前后缀不相同的情况
3. 处理前后缀相同的情况

class Solution {
public:
    void getNext(int* next, string& s){
        int j = -1;
        next[0] = j;
        for(int i=1; i<s.size(); i++){
            while(j >= 0 && s[i] != s[j+1]) // 前后缀不相同
                j = next[j]; // 就回退
            if(s[i] == s[j+1]) // 后缀相同
                j++;
            next[i] = j; // 将j(前缀的长度)赋给next[i]
        }
    }

    int strStr(string haystack, string needle) {
        int next[needle.size()];
        getNext(next, needle); // 获取next数组
        int j = -1;
        for(int i=0; i<haystack.size(); i++){
            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;
    }
};