KMP

KMP用来寻找字符串s中是否包含子串p

下标：    0 1 2 3 4 5 6 7 8 9 10
字符串s:  a b b a a b b a a b a
模式串p:  a b b a a b a
next数组: 0 0 0 1 1 2 1
next[i]为模式串已i结尾的 子串的后缀 和 模式串的前缀 匹配的个数
abbaaba的
前缀(从前往后看) a ab abb abba abbaa abbaab
后缀(从后往前看) a ba aba aaba baaba bbaaba

当匹配到下标j==6时，a!=b，但是我们已知0~5是匹配的&&next[5]==2，
那么我们将接着再从j==6,i==2开始匹配

下标：    0 1 2 3 4 5 6 7 8 9 10
字符串s:  a b b a a b b a a b a
模式串p:          a b b a a b a
next数组:         0 0 0 1 1 2 1

例题

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

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

class Solution {
 public:
  int strStr(string s, string p) {
    int n = s.size(), m = p.size();
    vector<int> next(m, 0);
    // i是长度
    // j是下标，从1开始
    for (int i = 0, j = 1; j < m; ++j) {
      // i = next[i - 1] 可理解为，当i不能继续增加时，我们尝试之前的（次大的）匹配长度，并匹配新的p[i]和p[j]
      // 
      // 如下 ? 处，i==6 a!=z，我们还知道s[0,5] == s[7,12]
      // 6是长度对应next下标5，next[6 - 1] = next[5] = 4 意味着在s[7,12]次长的匹配长度为4
      //
      // p     a  b  a  b  a  b  z  a  b  a  b  a  b  a
      // next  0  0  1  2  3  4  0  1  2  3  4  5  6  ?
      // index 0  1  2  3  4  5  6  7  8  9  10 11 12 13
      while (i > 0 && p[i] != p[j]) i = next[i - 1];
      if (p[i] == p[j]) ++i;
      next[j] = i;
    }

    for (int i = 0, j = 0; j < n; ++j) {
      while (i > 0 && p[i] != s[j]) i = next[i - 1];
      if (p[i] == s[j]) ++i;
      if (i == m) return j - m + 1;
    }

    return -1;
  }
};

参考

https://www.zhihu.com/question/21923021/answer/37475572 https://kb.cnblogs.com/page/176818/

KMP

例题​

参考​

例题

参考