https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

KMP算法

https://blog.csdn.net/Y_Vollerei/article/details/135686184?spm=1001.2014.3001.5501

https://programmercarl.com/0028.实现strStr.html#算法公开课

<aside> 💡

KMP算法的核心思想：当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了

KMP算法的代码实现

分为两个部分：

1. 求模式串的next数组
2. 使用next数组进行模式串与主串的匹配 </aside>

vector<int> getNext(string s) {
	// 主要注意next[0]初始化为0（第一个字符不存在前后缀，next一定为0）
	vector<int> next(s.size(), 0);
	// j指向前缀末尾，初始化为0（从首个字符开始判断）
	int j = 0;
	
	// i指向后缀末尾，初始化为1（第一个字符不需要判断，从第二个字符开始比较子串的前后缀）
	for (int i = 1; i < s.size(); ++i) {
		// 处理前后缀不相同的情况
		// 如果发生冲突且j还能回退的话则继续回退
		// 如果j已经回退到首字母，且首字母也冲突时退出回退循环
		while (j > 0 && s[i] != s[j]) {
			j = next[j-1];
		}
		// 处理前后缀相同的情况
		// 匹配成功则j后移，此时j之前的子串即为最长相等前缀，将其赋值给next[i]
		// ++i（进入下一次循环自动实现）
		if (s[i] == s[j]) {
			next[i] = ++j;
		}
	}
	return  next;
}

// 思路与获取next数组差不多（获取next数组的过程相当于模式串的后缀与前缀匹配）
int strStr(string haystack, string needle) {
	vector<int> next = getNext(needle);
	int j = 0;

	for (int i = 0; i < haystack.size(); ++i) {
		// 发生冲突时j进行回退（这步的目的是利用匹配失败后的信息，减少下一次匹配的工作量）
		while (j > 0 && haystack[i] != needle[j])
			j = next[j - 1];
		// 匹配成功时j后移
		if (haystack[i] == needle[j]) 
			++j;
		// 如果此时j等于模式串长度说明找到了模式串在子串内的位置，进行返回
		if (j == needle.size()) 
			return i - needle.size() + 1;
	}
	return -1;
}