京公网安备11010502063487号在字符串 haystack 里找到字符串 needle 第一次出现的起点下标，找不到返回 -1。最直接的做法是对每个起点逐字符比较，最坏是 O(n·m)；KMP 算法在失配时不回退 haystack 的指针，只依据 needle 自身的前缀结构把匹配长度退回去，总时间 O(n + m)。本文给出 KMP 的五种语言实现，用真实的字符比较次数和耗时展示两者在最坏输入上的差距，并把 KMP 的匹配和回退做成分步演示。
完整题目见官方页面（链接在文末）。needle 不为空。基准解是最朴素的两层循环：对每个起点，从头逐字符比较。它是最易于检查正确性的写法，与 KMP 完全不同。一共 12 组用例，覆盖：官方示例、找不到、needle 比 haystack 长、单字符、重复片段多的字符串：
输入 ["sadbutsad","sad"] 输出 0 输入 ["leetcode","leeto"] 输出 -1 输入 ["a","a"] 输出 0 输入 ["a","b"] 输出 -1 输入 ["abc","abcd"] 输出 -1 输入 ["aaaaa","aab"] 输出 -1
逐个起点比较的最坏情形是：haystack 全是 a，needle 是一长串 a 再加一个 b。每个起点都会比较到 needle 的最后一个字符才失配，然后整个比较作废、起点前移一格。下面是两种做法真实统计的字符比较次数：
字符比较次数：haystack = a*n，needle = a*(n/2-1)+b（最坏情形） n= 500: 逐个起点比较 62750 次 KMP 1248 次 n= 1000: 逐个起点比较 250500 次 KMP 2498 次 n= 2000: 逐个起点比较 1001000 次 KMP 4998 次 n= 4000: 逐个起点比较 4002000 次 KMP 9998 次
n 每翻一倍，逐个起点比较的次数增加约 4 倍（62750、250500、1001000、4002000），是平方增长；KMP 的比较次数是 1248、2498、4998、9998，每翻一倍只翻一倍，是线性增长。n = 4000 时，逐个起点比较用了 400 万次，KMP 只用了不到 1 万次。
先算前缀表 lps：lps[i] 是 needle[0..i] 最长的"既是前缀又是后缀"的真前缀的长度。匹配时 k 表示已经匹配了 needle 的前 k 个字符：当前字符相同就 k 加一；失配就把 k 退到 lps[k-1]，重新比较当前字符，haystack 的下标一直不回退。k 等于 needle 的长度时匹配成功。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(haystack, needle): m = len(needle) lps = [0] * m # lps[i]：needle[0..i] 最长的"既是前缀又是后缀"的真前缀长度 k = 0 for i in range(1, m): while k and needle[i] != needle[k]: k = lps[k - 1] if needle[i] == needle[k]: k += 1 lps[i] = k k = 0 # k：当前已经匹配了 needle 的前 k 个字符 for i, ch in enumerate(haystack): while k and ch != needle[k]: # 失配：不回退 haystack，只把 k 退到 lps[k-1] k = lps[k - 1] if ch == needle[k]: k += 1 if k == m: return i - m + 1 return -1
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["sadbutsad","sad"] → 0 ["leetcode","leeto"] → -1 ["a","a"] → 0 ["a","b"] → -1 ["abc","abcd"] → -1 ["aaaaa","aab"] → -1
Java · 解法代码class Solution { public int strStr(String haystack, String needle) { int m = needle.length(); int[] lps = new int[m]; // lps[i]：needle[0..i] 最长的"既是前缀又是后缀"的真前缀长度 for (int i = 1, k = 0; i < m; i++) { while (k > 0 && needle.charAt(i) != needle.charAt(k)) k = lps[k - 1]; if (needle.charAt(i) == needle.charAt(k)) k++; lps[i] = k; } int k = 0; // k：当前已经匹配了 needle 的前 k 个字符 for (int i = 0; i < haystack.length(); i++) { while (k > 0 && haystack.charAt(i) != needle.charAt(k)) k = lps[k - 1]; // 失配：只退 k，不回退 i if (haystack.charAt(i) == needle.charAt(k)) k++; if (k == m) return i - m + 1; } return -1; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["sadbutsad","sad"] → 0 ["leetcode","leeto"] → -1 ["a","a"] → 0 ["a","b"] → -1 ["abc","abcd"] → -1 ["aaaaa","aab"] → -1
Go · 解法代码func strStr(haystack, needle string) int { m := len(needle) lps := make([]int, m) // lps[i]：needle[0..i] 最长的"既是前缀又是后缀"的真前缀长度 for i, k := 1, 0; i < m; i++ { for k > 0 && needle[i] != needle[k] { k = lps[k-1] } if needle[i] == needle[k] { k++ } lps[i] = k } k := 0 // k：当前已经匹配了 needle 的前 k 个字符 for i := 0; i < len(haystack); i++ { for k > 0 && haystack[i] != needle[k] { // 失配：只退 k，不回退 i k = lps[k-1] } if haystack[i] == needle[k] { k++ } if k == m { return i - m + 1 } } return -1 }
$ go build -o bin . && ./bin < cases.jsonl ["sadbutsad","sad"] → 0 ["leetcode","leeto"] → -1 ["a","a"] → 0 ["a","b"] → -1 ["abc","abcd"] → -1 ["aaaaa","aab"] → -1
JavaScript · 解法代码function strStr(haystack, needle) { const m = needle.length; const lps = new Array(m).fill(0); // lps[i]：needle[0..i] 最长的"既是前缀又是后缀"的真前缀长度 for (let i = 1, k = 0; i < m; i++) { while (k > 0 && needle[i] !== needle[k]) k = lps[k - 1]; if (needle[i] === needle[k]) k++; lps[i] = k; } let k = 0; // k：当前已经匹配了 needle 的前 k 个字符 for (let i = 0; i < haystack.length; i++) { while (k > 0 && haystack[i] !== needle[k]) k = lps[k - 1]; // 失配：只退 k，不回退 i if (haystack[i] === needle[k]) k++; if (k === m) return i - m + 1; } return -1; }
$ node run.js < cases.jsonl ["sadbutsad","sad"] → 0 ["leetcode","leeto"] → -1 ["a","a"] → 0 ["a","b"] → -1 ["abc","abcd"] → -1 ["aaaaa","aab"] → -1
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { public: int strStr(string haystack, string needle) { int m = needle.size(); vector<int> lps(m, 0); // lps[i]：needle[0..i] 最长的"既是前缀又是后缀"的真前缀长度 for (int i = 1, k = 0; i < m; i++) { while (k > 0 && needle[i] != needle[k]) k = lps[k - 1]; if (needle[i] == needle[k]) k++; lps[i] = k; } int k = 0; // k：当前已经匹配了 needle 的前 k 个字符 for (int i = 0; i < (int)haystack.size(); i++) { while (k > 0 && haystack[i] != needle[k]) k = lps[k - 1]; // 失配：只退 k，不回退 i if (haystack[i] == needle[k]) k++; if (k == m) return i - m + 1; } return -1; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["sadbutsad","sad"] → 0 ["leetcode","leeto"] → -1 ["a","a"] → 0 ["a","b"] → -1 ["abc","abcd"] → -1 ["aaaaa","aab"] → -1
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
haystack 是 n 个 a，needle 是 n/2 − 1 个 a 再加一个 b（上面的最坏情形），每个规模取三次中最快的一次：
haystack 长度 n（needle 长度 n/2） | 暴力解 | 本文解法
500 | 1.797 ms | 0.038 ms
1000 | 7.239 ms | 0.087 ms
2000 | 29.160 ms | 0.171 ms
4000 | 116.177 ms | 0.355 ms暴力解从 500 到 4000（8 倍）耗时增长约 65 倍，接近平方（64 倍）；KMP 增长约 9.3 倍，略高于线性（8 倍）。n = 4000 时，暴力解 116.2ms，KMP 0.36ms，约 327 倍。
Python 版本另外和朴素做法做了随机对拍。字母表只有 a、b，这样字符串里重复片段很多，最容易暴露失配回退的错误：
随机对拍 20000 组（字母表只有 a、b（这样重复片段很多，最容易暴露失配回退的错误），haystack 长 1 到 14，needle 长 1 到 5），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 haystack = "abxabcabcaby"、needle = "abcaby"。needle 的前缀表已经在上方给出。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。注意 haystack[8] 处的失配：k 从 5 退到 lps[4] = 2，而 haystack 的下标没有回退，needle 前两个字符 ab 已经被复用，不需要重新比较。