第一个匹配项的下标：失配后谁该回退
朴素法把已经比过的前缀整段扔掉，文本指针回退。KMP 用「已匹配前缀的最长真后缀」让模式滑动，文本指针只进不退。
朴素法：对每个文本起点逐一比对，失败则 i 回退重试，最坏 O(m·n)。KMP：先对模式计算 next 数组（最长相等真前后缀长度），匹配时失配则 j 跳到 next[j-1]，i 不回退，总时间 O(m+n)。
给你两个字符串 haystack 和 needle，在长串里找出短串第一次完整出现的起始下标。找不到返回 -1。必须连续、顺序一致，不能跳着取字符；只要最早的那一次，不要所有出现位置。
好认的例子：haystack = "sadbutsad"，needle = "sad"，开头三次全中，返回 0；末尾还有一段 sad，题目不要。haystack = "leetcode"，needle = "leeto"，每个窗口都在中途失败，返回 -1。
朴素法每个起点都从 needle 的第 0 个字符重新比。本文要回答："aaaaab" 配 "aab" 时，已经对齐的 a 为什么被整段扔掉；以及 "abababc" 配 "ababc" 时，next 怎样让 j 从 4 跳回 2，而文本指针停在原地。
朴素匹配：窗口失败，文本指针退回下一起点
第一反应就是滑动窗口：把 needle 贴到 haystack 的左边，对位比；失败就把窗口往右挪一格，再比。i 表示当前窗口在文本里的起点，j 表示模式里比到第几个字符。字符相等，i 和 j 同时前进；有一个不等，窗口起点加一，j 归零，从 needle[0] 重来。j 能走满 needle 的长度，返回这个起点。
"sadbutsad" 配 "sad" 在 i=0 三次全中，看起来瞬间结束——那是运气，看不出失败时做了多少重复劳动。换成演示里的 "aaaaab" 配 "aab" 才看得见账单。从 i=0 起：前两个 a 对上 aa，第三个文本是 a、模式要 b，失配。此时已经确认过的两格 a，下一个窗口全部作废。
失配后朴素法把 i 退到 1、j 归 0，从文本的第二个 a 对模式的第一个 a 重新比。前面那两格「已经对齐」被整段扔掉。窗口再失败，再退到 i=2，同一串 a 再比一遍。最坏情况 haystack 一大串 a、needle 是 aaaab，每个起点都先连着匹配一长串 a，最后差一个才失败，比较次数接近 (n-m+1)·m，这就是平方的来源。
暴力缺的不是正确性，是记忆。每个窗口独立，实现短，边界清楚，LC28 用它能过。缺口可以问成一句：刚才已经对齐成功的那一段里，有没有一段既是 needle 的前缀、又是这段的后缀？如果有，下一次不必从 needle[0] 比，可以从这个前缀的长度接着比。
回退朴素法把「已匹配的公共前缀」全部丢掉重来。"aaaaab" / "aab" 每次失配都要重走前面已匹配的 a。窗口之间不传记忆，这是最坏 O(m·n) 的根源。
KMP：文本指针不退，模式滑到已匹配前缀的后缀
匹配成功时 KMP 和暴力一样，文本和模式一起往前走。差别只在失配。暴力做「窗口起点加一、j 归零」；KMP 做 j = next[j-1]，文本下标 i 不动。含义：haystack 当前这个对不上的字符还留着，needle 滑到「已经匹配前缀」的位置，继续比这一个字符。
next[i] 表示模式前 i+1 个字符的最长相等真前后缀长度。真前缀、真后缀都不取整段自己，否则长度永远是整段，滑不动。对演示里的 needle = "ababc"：下标 0 的 a 没有真前后缀，next[0]=0；ab 的 a 和 b 不等，next[1]=0；aba 里 a 既是前缀也是后缀，next[2]=1；abab 里 ab 既是前缀也是后缀，next[3]=2；ababc 对不上更长的候选，next[4]=0。于是 next = [0, 0, 1, 2, 0]。
haystack = "abababc"，要找 "ababc"。i 从 0 走到 3，j 同步走到 4，已匹配 "abab"。下一步文本是 a、模式要 c，失配。暴力会把窗口挪到下一个起点，j 归零。KMP 看 next[3]=2：已经匹配的 "abab" 最长真前后缀是 "ab"，长度 2。意思是：文本里刚才那四格的后两格 ab，本来就等于 needle 的前两格。needle 直接滑到 j=2，i 仍停在失配的那个 a 上，继续拿 a 对 needle[2] 的 a。
后面 a/a、b/b、c/c 对齐，j 走到 5，模式走满，命中。起点是当前文本下标减去模式长度再加一，也就是 2。这一跳省掉的，是把已经确认过的 "ab" 再比一次。next 不是口诀，是「这段已经匹配的后缀，其实是 needle 的前缀」。计算 next 本身也是模式自己匹配自己，仍按「失配就按已算好的较短前缀回跳」，时间 O(m)，不是两两枚举。
短模式、没有自重叠时，加速接近零。"sad" 的 next 是 [0,0,0]，失配时 j 只能回 0，和暴力一样，正确性仍在。next 多 1 或少 1 不是「慢一点」，可能跳过真正的命中。先把暴力写对，再在失配处补这一跳。
前后缀已匹配的前缀如果和它的后缀相同，那后缀可以直接作为新的已匹配部分。"abab" 的最长真前后缀是 "ab"，所以失配后 j 从 4 收到 2，不必退回 0。
Go：KMP 前缀函数 + 匹配
func strStr(haystack, needle string) int {if needle == "" { return 0 }next := make([]int, len(needle))for i, k := 1, 0; i < len(needle); i++ {for k > 0 && needle[i] != needle[k] { k = next[k-1] }if needle[i] == needle[k] { k++ }next[i] = k}for i, j := 0, 0; i < len(haystack); i++ {for j > 0 && haystack[i] != needle[j] { j = next[j-1] }if haystack[i] == needle[j] { j++ }if j == len(needle) { return i - j + 1 }}return -1}
1空模式按约定返回 0，不要落到后面的循环里对空串下标。
2第一段循环是模式自己匹配自己，填 next。"ababc" 填完是 [0,0,1,2,0]。k 失配时按已经算好的较短前缀回跳，不从头枚举。
3第二段才是文本和模式比。haystack 的 i 只增不减。失配时 j = next[j-1]，"abababc" 在 j=4 对不上 c 时，j 收到 2，i 仍停在那个 a。
4j 走满 needle 的长度，返回起点 i-j+1。演示里命中时起点是 2。全部走完还没满，返回 -1。
总结
朴素法失配就让文本回退；KMP 用 next 让模式滑动，i 不回退。"ababc" 失配后 j 从 4 跳到 2。
- "aaaaab" / "aab" 每次失配都扔掉已匹配的 a，窗口之间不传记忆，最坏平方。
- next[i] 是模式前 i+1 个字符的最长相等真前后缀长度。真前后缀不取整段自己。
- 失配 j = next[j-1]，文本指针不动。短模式没有自重叠时加速接近零，正确性仍在。