1. KMP 算法介绍

1.1 暴力方法

暴力方法就是将两个字符串进行一个一个比较

这个知道就行了, 我们的重点是 KMP 算法

1.2 KMP 算法介绍

暴力方法的时间复杂度是：O(n * m), 使用 KMP 算法可以将时间复杂度优化到：O(n + m).
暴力方法时间慢的原因是：每一个匹配的过程都是相互独立的, 所以每次都要重新比对一遍.

KMP 算法就是利用前面的匹配过程来加速后面的匹配过程.

2. next 数组的定义

next数组：不包含当前下标在内, 其前面的字符串的前缀与后缀的最大匹配长度.(不能含有整体).

我们这里只是讲解 next数组 的定义, 后面会讲解如何快速得到 next数组.

求解 next数组 的例子：

a  a  b  a  a  b
0  1  2  3  4  5我们下面的“前缀, 后缀”都代表的是“最大的前缀, 最大的后缀”匹配.首先下标为：
0 下标：因为前面没有任何数字, 所以对应的 next 数值为： -1.(人为规定的).
1 下标：前面只有一个“a”, 那么前缀是“a”, 后缀也是“a”, 但是有不能包含整体, 所以是： 0.
2 下标：前面有的是“a a”, 那么前缀是“a”(前面的 a), 后缀也是“a”(后面的 a),没有包含整体, 是 1
3 下标：前面有“a a b”, 没有前缀与后缀相同的情况, 所以是： 0.
4 下标：前面有“a a b a”, 那么前缀是“a”, 后缀是“a”, 所以是： 1.
5 下标：前面有“a a b a a”, 前缀是：“aa”, 后缀是“aa”, 所以是： 2.无论是哪一个字符串, 0 1 下标的字符对应的next值是：-1 0.

3. 匹配过程利用 next 数组加速的图解

如上图所示的两个字符串

我们要从 S1 中找到 S2, 0 ~ 12 都能匹配, 但是从 13 开始不行了, 要是按照暴力方法, 那么我们需要从 0, 1, 2, 3 ... 开始不停匹配.

但是我们现在有了 next 数组,

从 13 开始不匹配, 那么 next 数组对应的数字为：6.
所以, 我们直接将 S2 中下标为 6 的位置与 S1 中下标为 13 的位置匹配. 而且前面的下标：0 ~ 5 的位置一定是可以匹配上的.

因为 next数组 的 6 已经确定了 S2 中的(0 ~ 5)位置 和 (7 ~ 12)位置 是相同的. 而且从刚刚的匹配过程也知道：S1 与 S2 的 (0 ~ 12) 下标位置代表的值肯定相同, 所以 S2 中的(7 ~ 12)位置 与 S1的(7 ~ 12) 位置一定是相同的(不然为什么到了 13 才停止), 那么我们又通过 next数组 知道：S2 中的(0 ~ 5)位置 和 (7 ~ 12)位置 是相同的, 所以 S2 中的(0 ~ 5)位置肯定 与 S1 中的(7 ~ 12)位置 是相同的. 所以我们直接将 S2 中的(0 ~ 5)位置移动到S1 中的(7 ~ 12)位置, 继续比较 S1下标为：13位置的字符 与 S2下标为：6位置的字符 就行了.

此时, S1 的 13位置表示的字符还是 和 S2 的 6位置不相同, 所以继续执行上述过程, 我们找 S2 的 next数组 中的值：3, 将 S2 下标为：3 位置的字符 与 S1 下标为 13 位置的字符比较, 如下图：

若是后面还有没有匹配上的, 还是按照上述过程进行执行就行了, 这里只是举一个例子, 后续的情况不再说明

4. 第一个理解核心：新开头节省了匹配步骤

这个问题前面也已经有了详细的解释, 根据 next数组中数值 的定义, 就能确定从无法匹配上的那一个字符对应的 next 数值, 就是当前字符之间所有匹配的最大长度, next数组 中数值的另一个含义是：前缀的下一个字符在 7 位置(用下图当例子).

5. 第二个理解核心：如何保证两个字符串中间没有任何一个能匹配成功的(为什么可以直接跳过)

我们假设 S1 与 S2 到 j(k) 位置才不相同的(S1是j, S2是k) j == k. 只是表示不一样. 我们假设此时 j(k)位置对应的next数值是：7.

前提：next数组 中所有的数值全部正确.

我们假设从 S1的(i ~ p) 之间随便找一个“点：?”(位置), 然后往后一直到了 j - 1 位置与 S2 中 ? ~ j - 1 位置也一定是相同的, 那么我们既然想将 S2 的 0 位置移动到 S1 的 ? 位置, 那么 S2的(0 ~ j - 1) 位置必须是和 S1 的(? ~ j - ?) 位置是完全匹配的, 如下图的两个“红色虚线”, 但是这样是自相矛盾的. 因为这就是 next数值 的含义, 这样就表示你的 next数值 > 7, 但是我们的前提就是 next数组中所有的数值都正确. 对应的 next数值 == 7, 没有任何问题, 所以一定不可能 > 7, 所以自相矛盾, 不存在这样的 ?点.

6. 匹配过程 + 理解核心 + 代码再次图解

6.1 图解过程

6.2 代码实例

该有的解释, 都在代码中的注释中写好了.

public static int kmp(char[] s1, char[] s2) {  // s1中当前比对的位置是x  // s2中当前比对的位置是y  int n = s1.length, m = s2.length, x = 0, y = 0; // x, y不是值, 是下标.  int[] next = nextArray(s2, m);  // 得到next数组  // O(m)    // O(n)  while (x < n && y < m) {    // x < n：表示S1已经超出了比对的范围, 说明S1 没有 S2.       // y < m：表示S2已经来到了 m 之外的位置(越界), 那么说明必然已经匹配成功了.  if (s1[x] == s2[y]) {// 若是相等, x, y一起++.  x++;  y++;  } else if (y == 0) { // 不能往前跳了.  // 只将 x++, 下一个位置与 y == 0 位置相比较  x++;  } else {  // 还能继续往前跳,   y = next[y];  // 直接让y来到next[y]位置.  }  }  return y == m ? x - y : -1;  // 若是发现y越界了, 就返回开头, 因为已经找到了位置.  // 若是y没有越界, 那么只有一种情况, x越界了, 说明S1 中 没有S2, 直接返回 -1.}

7. next 数组快速生成

7.1 例 1 (不用跳)

7.2 跳跃多次的例子

8. 理解核心 3：解释为什么从 cn 往前跳

加速创建 next数组 的过程本质就是找两段相同的字符, 而且这两段字符之间必须要有间隔字符, 这个间隔字符若是和 当前的前一个字符 相同, 那么说明 前面一段的字符加上间隔字符 与 后面一段的字符加上当前的前一个字符 是相同的, 那么就说明这段字符的长度就是 next数值.

若是第一次没有匹配上, 那么可以直接判断下一个中间字符(通过 next 数值找到的) 是不是相同, 这样就加速了 next数组 的创建速度.

9. 代码实例

public static int[] nextArray(char[] s, int m) { // m：S2的长度.  if (m == 1) {     // 如果 m == 1, 说明只有一个next数值, 就直接返回 -1.       return new int[] { -1 };  }  int[] next = new int[m]; // 创建一个 S2长度的数组  next[0] = -1;   // 这两个值都是能直接确定的.  next[1] = 0;  // i表示当前要求next值的位置  // cn表示当前要和前一个字符比对的下标  int i = 2, cn = 0;  while (i < m) {       // 每一个字符的匹配.   if (s[i - 1] == s[cn]) { // cn所在的位置的字符 == 当前位置的前一个字符.  next[i++] = ++cn;  } else if (cn > 0) {  // 还能往前跳.  cn = next[cn];  } else {  next[i++] = 0;  // 继续去下一个位置寻找next值.  }  }  return next;  // 最后返回创建好的next数组  
}

10. 时间复杂度分析

10.1 nextArray 函数分析

假设这个字符串长度为：m, 那么时间复杂度是：O(m).

此时有两个量(人为规定的)：i, i - cn.

i的范围是：0 ~ m, i - cn的范围是：0 ~ m.

在这个函数中, 无非只有三个分支(三种情况)：

1. 第一个分支：i变大, i - cn 不变.
2. 第二个分支：i不变, i - cn 变大.
3. 第三个分支：i变大, i - cn 变大.

那么说明这两个变量没有减小的时候, 只能变大, 那么只要求出最大能有多少, 就可以知道时间复杂度了：i + i - cn <= 2m, 所以这个函数的时间复杂度是：O(2m) -> O(m).

10.2 KMP 匹配过程的时间复杂度

也是和上面一样：S1 的下标是 x(最大是n), S2 的下标是：y, x - y(最大是n).

在这个函数中, 无非只有三个分支 (三种情况)：

1. 第一个分支：x变大, x - y 不变.
2. 第二个分支：x变大, x - y 变大.
3. 第三个分支：x不变, x - y 变大.

同样的, x 与 x - y 永远都是递增的, 所以我们只需要求出 x + x - y 的最大值就是时间复杂度了.
x + x - y <= 2n, 所以这个函数的时间复杂度是：O(2n) -> O(n).

所以 KMP 算法整体的时间复杂度是：O(n + m).

经过了上述过程, 最好还是自己写几个字符串匹配一下, 若是不相信自己, 可以写几个字符串用编译器调试. 第一二个理解核心都比较好理解, 但是第三个理解核心若是没有几个例子可能无法在自己脑子里形成一个完整的逻辑链. 所以最好还是写几个字符串匹配调试一下.

11. 附加题目：判断子树

11.1 暴力方法

逻辑上的实现就是直接一个头节点一个头节点的遍历就行了, 但是对应的, 这样的时间复杂度是 O(n*m).

代码实例

// 暴力递归  
// 时间复杂度O(n * m)  
public static boolean isSubtree(TreeNode t1, TreeNode t2) {  if (t1 != null && t2 != null) {  return same(t1, t2) || isSubtree(t1.left, t2) || isSubtree(t1.right, t2);  }  // 三种情况// t1 == null && t2 == null, 这样肯定是在的, 所以返回true// t1 == null && t2 != null, 这样肯定是不存在的, 返回false// t1 != null && t2 == null, 这样肯定是存在的, 返回true.return t2 == null;  
}  // 判断a和b这两棵树是否完全一样  
public static boolean same(TreeNode a, TreeNode b) {  if (a == null && b == null) {  return true;  }  if (a != null && b != null) {  return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);  }  return false;  
}

11.2 利用 KMP 算法(最优解)

这个方式的时间复杂度是 O(n + m).

首先, 需要掌握将二叉树序列化的方法, 这个在以前讲过, 所以我们直接给出代码, 不再讲解

public static void serial(TreeNode head, ArrayList<String> path) {  if (head == null) {  path.add(null);  } else {  path.add(String.valueOf(head.val));  serial(head.left, path);  serial(head.right, path);  }  
}

序列化的正确性!!!(这样也是可以保证可以判断两棵子树的).

总流程：
可以类比一下 char[], 只是其中的字符变成了 String 而已.
唯一需要注意的就是 String 的比较, 毕竟字符串的比较和字符的比较是不同的.

// 二叉树先序序列化 + KMP算法匹配  
// 时间复杂度O(n + m)  
public static boolean isSubtree2(TreeNode t1, TreeNode t2) {  if (t1 != null && t2 != null) {  ArrayList<String> s1 = new ArrayList<>();  // 利用集合的形式(内部实现是数组)存储字符串.ArrayList<String> s2 = new ArrayList<>();  serial(t1, s1);  // 序列化两棵树.serial(t2, s2);  return kmp(s1, s2) != -1;  // 若是最后利用KMP算法返回的值是 -1. 说明t1中存在t2.// 若是最后利用KMP算法返回的不是 -1, 说明t2中存在t1.}  return t2 == null;  // 这里和上面是一样的, 不再解释
}

KMP 算法流程

public static int kmp(ArrayList<String> s1, ArrayList<String> s2) {  int n = s1.size(), m = s2.size(), x = 0, y = 0;  int[] next = nextArray(s2, m);  while (x < n && y < m) {  if (isEqual(s1.get(x), s2.get(y))) {  // 只有这里不一样, isEqual函数下面有x++;  y++;  } else if (y == 0) {  x++;  } else {  y = next[y];  }  }  return y == m ? x - y : -1;  
}

快速生成 next数组：

public static int[] nextArray(ArrayList<String> s, int m) {  if (m == 1) {  return new int[] { -1 };  }  int[] next = new int[m];  next[0] = -1;  next[1] = 0;  int i = 2, cn = 0;  while (i < next.length) {  if (isEqual(s.get(i - 1), s.get(cn))) {  // 也是只有这里不一样, isEqual函数下面有next[i++] = ++cn;  } else if (cn > 0) {  cn = next[cn];  } else {  next[i++] = 0;  }  }  return next;  
}

比较两个 字符串 是不是相等

public static boolean isEqual(String a, String b) {  if (a == null && b == null) {  return true;  }  if (a != null && b != null) {  return a.equals(b);  }  return false;  
}