要解决的问题：

s1字符串是否包含s2字符串，如果包含返回s1中包含s2的最左开头位置，不包含返回-1（当然也可以返回s1中包含s2的所有开头位置）

暴力方法就是s1的每个位置都做开头，然后去匹配s2整体，时间复杂度O(n * m)

KMP算法可以做到时间复杂度O(n + m)

算法讲解需要分为5个部分：

理解next数组的定义，定义是一切的关键，前缀和后缀的最大匹配长度
假设已经有了next数组，详解匹配过程是如何得到加速的，加速过程有2个理解核心
理解了匹配主流程之后，详解next数组如何快速生成，不停跳跃的过程有1个理解核心
KMP算法代码详解，主流程 + next数组生成
时间复杂度O(n)的证明，直接从代码层次就可以分析出来，分析方式好理解，但是比较特别

next数组的定义

next[i] 表示模式串中从开头到索引 i 的子串（即 pattern[0...i]）中，最长的相同前缀和后缀的长度。这里的“前缀”和“后缀”指的是：

前缀：子串从开头开始的一段连续字符，但不包括整个子串本身。
后缀：子串从结尾结束的一段连续字符，但不包括整个子串本身。
“相同”意味着前缀和后缀的字符序列完全一样。

以模式串 "ABABAC" 为例，逐步计算 next 数组：

索引 i	字符	子串	最长相等前后缀	`next[i]`
0	A	‘’	无（长度<1）	-1
1	B	A	无	0
2	A	AB	无	0
3	B	ABA	A	1
4	A	ABAB	AB	2
5	C	ABABA	ABA	3
6(这是补充的)	ABABAC	没找到	无	0

注：

在某些实现中，为了方便，next 数组可能会整体左移一位，并将 next[0] = -1，表示当首字符失配时直接移动到模式串开头。这种变体在代码实现中更常见。
计算前后缀不能要整体（不包括整个子串本身）。

为了方便，一般记录next[0] = -1, next[1] = 0

练习，aabaabsaabaaa的next数组是？

答案：next = [-1, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 2]

如何用next数组加速模式的匹配

例子：s1='aabaabcaabaaba'，s2='aabaabcaabaabt'

首先求得s2的next数组是(不包含最终补充的位置)：[-1, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6]

看左神的例子就可以理解为什么要搞最长前后缀匹配了。

视频精准空降链接

再补几张图：

下面是2个理解核心：

最后回顾这个例子：

KMP算法代码

public static int kmp(char[] s1, char[] s2){
    int n = s1.length, m = s2.length, x = 0, y = 0;// x是主串的指针，y是模式串的指针
    int[] next = nextArray(s2, m);
    while(x < n && y < m){
        if (s1[x] == s2[y]){// 如果主串当前字符 s1[x] 等于模式串当前字符 s2[y]，说明匹配成功，接着往下匹配
            x++;// 当前字符匹配，继续比较下一个字符，两个指针都往前移动
            y++;
        }else if(y == 0){ // 连模式串的第一个字符都匹配不上，无法再回退
            x++; // 只能移动主串指针 x++，继续尝试从主串的下一个位置开始匹配，且模式串指针 y 保持为 0
        }else { // 如果失配且 y > 0，说明模式串已经匹配了一部分字符，但是当前位置不匹配
            y = next[y]; //利用next数组。直接利用已匹配的前缀继续比较，避免重复匹配
        }
    }
    return y == m? x - y : -1;// 如果找到匹配，返回模式串在主串中的起始位置（x - y）；否则返回 -1。
}

其中生成next数组的函数nextArray将在下面总结。

如何快速生成next数组

不停跳跃的过程有1个理解核心：精准的视频空降链接

首先前3位可以快速确定:

next[0] = -1
next[1] = 0
只需要看最前面这2个字符是不是一样，一样就是1，不一样就是0。比如AAC...，那么C对应的next就是1，比如ABD，那么D对应的next就是0（next数组的定义）

然后就是一些情况的讨论：

1.不用跳：

2.跳1，2，3次，甚至跳到头了：

一个核心理解就是：（其实还是用了next数组的定义，这是最核心的！！）

next数组生成代码

它的精髓在于高效地利用模式串自身的结构，通过动态规划和回退机制快速构建 next 数组。

public static int[] nextArray(char[] 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;//i是当前要求next值的位置，cn表示当前要和哪个位置的值进行比对
    while (i < m){
        if (s[i - 1] == s[cn]){// 如果前一个字符 s[i-1] 与当前前缀位置的字符 s[cn] 相等，说明可以扩展相等前后缀
            next[i++] = ++cn;
        }else if (cn > 0){// 当前前缀还有回退的空间
            cn = next[cn];// 回退到当前前缀的次长相等前后缀位置，继续尝试匹配
        }else { // 已经回退到开头，无法再找到更短的相等前后缀
            next[i++] = 0;
        }
    }
    return next;
}

时间复杂度证明

时间复杂度O(n)的证明，直接从代码层次就可以分析出来，分析方式好理解，但是比较特别

视频精准空降链接

next数组生成的时间复杂度分析：

或者：虽然有 while 循环和回退，但 i 只增不减，cn 的总回退次数不会超过 i 的增加次数

kmp算法的时间复杂度分析：

重要：以后可以认为，求解1个位置的next数组的值，时间复杂度O(1)

力扣

28. 找出字符串中第一个匹配项的下标(KMP算法的实现)

时间复杂度O(n + m)

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

注：Java中s1.indexOf(s2)效率可能比KMP更高。（因为JVM会优化）

我这题写的答案：

class Solution {
    public int strStr(String haystack, String needle) {
        char[] s1 = haystack.toCharArray();
        char[] s2 = needle.toCharArray();
        int n = s1.length, m = s2.length, x = 0, y = 0;
        int[] next = nextArray(s2, m);
        while (x < n && y < m) {
            if (s1[x]==s2[y]){
                x++;
                y++;
            }else if(y == 0){
                x++;
            }else {
                y = next[y];
            }
        }
        return y == m ? x - y : -1;       
    }

        public static int[] nextArray(char[] 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 < m) {
            if (s[i - 1] == s[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}

如果用java的indexOf呢：

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle); 
    }
}

572. 另一棵树的子树

给你两棵二叉树root和subRoot 检验root中是否包含和subRoot具有相同结构和节点值的子树如果存在，返回true 否则，返回false

本题需要理解二叉树先序序列化，讲解036，题目5

方法1:暴力解

暴力递归，时间复杂度O(n * m)，其中n是root的节点数目，subRoot是子树的节点数目。

注意条件：（假设t1 是 Root, t2是subRoot）

如果t1 == null,t2 != null则返回False
如果t1 == null，t2 == null，返回True
如果t1 != null， t2 == null，返回True
如果t1和t2都不是null，那么就要暴力递归判断

综上把前面三种情况可以总结为返回是否判断t2 == null。(下面代码第5行)

代码如下：

public static boolean isSubTree_Traversal(TreeNode t1, TreeNode t2){
    if (t1 != null && t2 != null){
        return isSame(t1, t2) || isSubTree_Traversal(t1.left, t2) || isSubTree_Traversal(t1.right, t2);
    }
    return t2 == null;
}

其中isSame方法如下：

如果t1 == null && t2 == null返回true（写在一开始）
如果t1 == null || t2 != null返回false
如果t1 != null && t2 == null返回false
具体比较每个节点（写在中间）

中间2个条件就作为return false

/**
 * 判断两棵二叉树是否相同
 * 
 * @param t1 第一棵二叉树的根节点
 * @param t2 第二棵二叉树的根节点
 * @return 如果两棵二叉树相同返回true，否则返回false
 */
public static boolean isSame(TreeNode t1, TreeNode t2){
    // 如果两棵树的根节点都为空，则认为两棵树相同
    if (t1 == null && t2 == null) return true;
    
    // 如果两棵树的根节点都不为空，进一步比较它们的值及子树
    if (t1 != null && t2 != null){
        // 两棵树相同需满足：根节点值相同，且左右子树分别相同
        return t1.val == t2.val && isSame(t1.left, t2.left) && isSame(t1.right, t2.right);
    }
    
    // 如果一个根节点为空，另一个不为空，则认为两棵树不同
    return false;
}

两个函数都用了递归还是挺快的。

方法2:先序序列化+KMP

时间复杂度O(n + m)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root != null && subRoot != null) {
            ArrayList<String> s1 = new ArrayList<>();
            ArrayList<String> s2 = new ArrayList<>();
            serial(root, s1);
            serial(subRoot, s2);
            return kmp(s1, s2) != -1;
        }
        return subRoot == null;
    }

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

    public int kmp(ArrayList<String> s1, ArrayList<String> s2) {
        int n = s1.size(), m = s2.size(), x = 0, y = 0;
        // 求next 数组
        int[] next = nextArray(s2, m);
        while (x < n && y < m) {
            if (isEqual(s1.get(x), s2.get(y))) {
                x++;
                y++;
            } else if (y == 0) {
                x++;
            } else {
                y = next[y];
            }
        }
        return y == m ? x - y : -1;
    }

    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 < m) {
            if (isEqual(s.get(i - 1), s.get(cn))) {
                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;
    }
}

这道题数据量小了，所以效果就是一般：

100 KMP算法原理和代码详解