KMP

该算法厉害的地方在于，匹配失败的时候，通过一个额外数据进行了剪枝，使得匹配的数量大大减小。
基于的核心逻辑是：
对于匹配串的任意一个位置而言，由该位置发起的下一个匹配点位置其实与原串无关。说白了就是，其实匹配失败应该跳转到哪的核心是自己和自己匹配，假设某个位置匹配失败我应该去哪？
因此next数组的理解就是：

  1. 需要两个指针，因为其实与自己进行匹配的核心问题在于，匹配失败的元素，与上一个元素是否相同，这是dp的思路，因为，我们其实用到了过去的多个状态，而状态的链条汇总在了上一个元素。即：与前一个元素有关的dp问题
  2. 与自己匹配的思考的地方在于，前缀与后缀究竟能匹配多少？这直接决定了在我后缀能够成功匹配的同时，下一个元素匹配失败了，应该跳转到哪个前缀？

三叶的是，其中一种next数组的匹配法则：匹配下一位失败时看上一位的next
两个元素相同时，自然的双指针递进。另外，next[i]的定义其实是，[0..=i]范围内，前缀后缀重合的最大长度。记录的是长度的原因是，还是我们希望跳到最能匹配后缀的前缀上，而因为是自己和自己匹配，因此其实只需要记录数量。
image.png
这样的指针移动起始是n-1类型dp（或者说状态机）

  • 如果p[i] == p[j]，有个逻辑在这，对于任何i结尾的字串，其next是j+1，因为我们维护j的位置是上一次匹配完毕，后缀有着相同的前缀的位置！！所以j++的迭代，所以多了一个相同的之后，只需要简单地j+1
  • 如果p[i] ！= p[j]，如下面，我应该找到上一个匹配到前缀的后缀.
    • 此时如果能够挪动j找到相同的元素，next[j]存储着以j结尾的字串的与后缀相同最大相同前缀，因此就可以直接j+1。保证这一点的是挪动的顺序，j=next[j-1]意味着，移动到j-1结尾的字串的与后缀相同最大相同前缀。思考abaab与abacb的创建过程就清楚了
    • 如果不能找到，显然就是没有前缀与其匹配，那么数量就是0

image.png
image.png
image.png

实现细节

匹配串pp前面加上一个‘ ’是为了简化边界情况，因为我们正确的跳转应该是，当前j匹配失败，去找j-1的next值，因此可以初始化一个0在那里放着。
这也是核心逻辑：当前位置匹配失败，那么看前面一位结尾的字串是否存在前后缀重叠的情况。

  1. class Solution {
  2.     // KMP 算法
  3.     // ss: 原串(string)  pp: 匹配串(pattern)
  4.     public int strStr(String ss, String pp) {
  5.         if (pp.isEmpty()) return 0;
  7.         // 分别读取原串和匹配串的长度
  8.         int n = ss.length(), m = pp.length();
  9.         // 原串和匹配串前面都加空格，使其下标从 1 开始
  10.         ss = " " + ss;
  11.         pp = " " + pp;
  13.         char[] s = ss.toCharArray();
  14.         char[] p = pp.toCharArray();
  16.         // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
  17.         int[] next = new int[m + 1];
  18.         // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
  19.         for (int i = 2, j = 0; i <= m; i++) {
  20.             // 匹配不成功的话，j = next(j)
  21.             while (j > 0 && p[i] != p[j + 1]) j = next[j];
  22.             // 匹配成功的话，先让 j++
  23.             if (p[i] == p[j + 1]) j++;
  24.             // 更新 next[i]，结束本次循环，i++
  25.             next[i] = j;
  26.         }
  28.         // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
  29.         for (int i = 1, j = 0; i <= n; i++) {
  30.             // 匹配不成功 j = next(j)
  31.             while (j > 0 && s[i] != p[j + 1]) j = next[j];
  32.             // 匹配成功的话，先让 j++，结束本次循环后 i++
  33.             if (s[i] == p[j + 1]) j++;
  34.             // 整一段匹配成功，直接返回下标
  35.             if (j == m) return i - m;
  36.         }
  38.         return -1;
  39.     }
  40. }

rust实现，其实next数组关键点就两个：

  1. next[i]表示i结尾的子串中，前缀后缀相同的数量
  2. 遇见不同，查看上一个前缀串中是否有相同的，没有的话，再找再上一个前缀
    1. /// kmp算法，28题，找到出现子串的第一个位置
    2. pub fn str_str(haystack: String, needle: String) -> i32 {
    3.  let (ss, p) = (haystack.bytes().collect::<Vec<u8>>(), needle.bytes().collect::<Vec<u8>>());
    4.  // haystack: [a, b, e, a, b, a, b, e, a, b, f]
    5.  // 获取next数组，对于 needle:   [a, b, e, a, b, f], next:     [0, 0, 0, 1, 2, 0]
    6.  // 即next[i]表示i结尾的子串中，前缀后缀相同的数量
    7.  let mut next = vec![0; p.len()];
    8.  let mut j: usize = 0;
    9.  for i in 1..p.len() {
    10.      // 注意这里 j > 0 时候的判断
    11.      while j > 0 && p[i] != p[j]{
    12.          // 难理解的是这个过程，但是画个图就知道了 针对 abcabcad 子串，j位置始终是
    13.          // 匹配后缀的前缀的末尾多一个，比如在匹配到c相同的时候，j移动到了第二个a
    14.          // 那么这个过程本质上就是不断跳到上一个前缀串的末尾，不多一个
    15.          // 即遇见不同，查看上一个前缀串中是否有相同的，没有的话，再找再上一个前缀
    16.          j = next[j-1];
    17.      }
    18.      if p[i] == p[j] { j+=1; }
    19.      next[i] = j;
    20.  }
    21.  // 匹配过程
    22.  j = 0;
    23.  for i in 0..ss.len() {
    24.      while j > 0 && ss[i] != p[j] {
    25.          j = next[j - 1];
    26.      }
    27.      if p[j] == ss[i] { j += 1; }
    28.      if j == p.len() { return (i - j + 1) as i32; }
    29.  }
    30.  -1
    31. }