刷题时偶然遇到一个字符串匹配问题，正好之前 KMP 算法没搞很清楚，所以记录一下经典问题：
（因为符号太多了，所以后面直接截图省事

leetcode传送门

题解

算法的核心为前缀函数，记作 KMP 算法 - 图1，其定义如下：
对于长度为 m 的字符串 s ，其前缀函数表示 s 的子串 s[0:i] 的最长的相等的真前缀与真后缀的长度。特别地，如果不存在符合条件的前后缀，那么 KMP 算法 - 图2，其中真前缀与真后缀的定义为不等于自身的前缀与后缀。

image.png

如何求解前缀函数
长度为 m 的字符串 s 的所有前缀函数的求解算法的总时间复杂度是严格 O(m) 的，且该求解算法是增量算法，即我们可以一边读入字符串，一边求解当前读入位的前缀函数。
为了叙述方便，我们接下来将说明几个前缀函数的性质：

image.png
image.png
image.png
image.png

  1. class Solution {
  2.     public:
  3.     int strStr(string haystack, string needle) {
  4.         int n = haystack.size(), m = needle.size();
  5.         if (m == 0) {
  6.             return 0;
  7.         }
  8.         vector<int> pi(m);
  9.         for (int i = 1, j = 0; i < m; i++) {
  10.             while (j > 0 && needle[i] != needle[j]) {
  11.                 j = pi[j - 1];
  12.             }
  13.             if (needle[i] == needle[j]) {
  14.                 j++;
  15.             }
  16.             pi[i] = j;
  17.         }
  18.         for (int i = 0, j = 0; i < n; i++) {
  19.             while (j > 0 && haystack[i] != needle[j]) {
  20.                 j = pi[j - 1];
  21.             }
  22.             if (haystack[i] == needle[j]) {
  23.                 j++;
  24.             }
  25.             if (j == m) {
  26.                 return i - m + 1;
  27.             }
  28.         }
  29.         return -1;
  30.     }
  31. };
  33. // 作者：LeetCode-Solution
  34. // 链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
  35. // 来源：力扣（LeetCode）
  36. // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。