本文的网课内容学习自B站左程云老师的算法详解课程，旨在对其中的知识进行整理和分享~

网课链接：算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili

一.KMP算法模板

题目： 找出字符串中第一个匹配项的下标

算法原理

  • 整体原理
    • KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，用于在一个主字符串（文本串）中查找一个子字符串（模式串）的出现位置。其核心思想是利用已经匹配过的信息，避免在匹配失败时从头开始重新匹配，从而将时间复杂度从暴力匹配的O(n*m)降低到O(n+m)。
  • 具体步骤

    • 构建next数组：

      • next数组是KMP算法的核心，它记录了模式串中每个位置之前的子串的最长相同前缀和后缀的长度。
      • 定义：
        • next = -1（表示没有前缀和后缀）
        • next = 0（单个字符没有真前缀和后缀）
      • 计算next数组的过程：
        • 初始化i=2（当前计算的位置），cn=0（当前匹配的前缀长度）。
        • 如果s[i-1] == s[cn]，则next[i] = cn + 1，i和cn都加1。
        • 如果不相等且cn>0，则cn = next[cn]（回退到前一个匹配的位置）。
        • 否则，next[i] = 0，i加1。

    • 匹配过程：

      • 初始化x=0（文本串的当前匹配位置），y=0（模式串的当前匹配位置）。
      • 如果s1[x] == s2[y]，则x和y都加1。
      • 如果y == 0（模式串的第一个字符就不匹配），则x加1。
      • 否则，y = next[y]（利用next数组跳过已经匹配的部分）。
  • 复杂度分析
    • 时间复杂度：
      • 构建next数组：O(m)，其中m是模式串的长度。
      • 匹配过程：O(n)，其中n是文本串的长度。
      • 总时间复杂度：O(n + m)。
    • 空间复杂度：
      • 需要额外的O(m)空间存储next数组。
  • 示例
    • 假设：
      • 文本串s1 = "ABABABABC"，模式串s2 = "ABABC"。

    • 构建next数组：

      • s2 = "ABABC"，m=5。
      • next = -1，next = 0。
      • i=2：s='B' != s='A'，next=0。
      • i=3：s='A' == s='A'，next=1。
      • i=4：s='B' == s='B'，next=2。
      • i=5：s='C' != s='A'，cn=next=0；s='C' != s='A'，next=0。
      • next数组：[-1, 0, 0, 1, 2, 0]（通常next数组长度为m，这里为方便理解扩展到m+1）。

    • 匹配过程：

      • x=0,y=0：'A'=='A'，x=1,y=1。
      • x=1,y=1：'B'=='B'，x=2,y=2。
      • x=2,y=2：'A'=='A'，x=3,y=3。
      • x=3,y=3：'B'=='B'，x=4,y=4。
      • x=4,y=4：'A'!='C'，y=next=2。
      • x=4,y=2：'A'=='A'，x=5,y=3。
      • x=5,y=3：'B'=='B'，x=6,y=4。
      • x=6,y=4：'A'!='C'，y=next=2。
      • x=6,y=2：'A'=='A'，x=7,y=3。
      • x=7,y=3：'B'=='B'，x=8,y=4。
      • x=8,y=4：'C'=='C'，x=9,y=5（y==m，匹配成功）。
      • 返回x-y=4（模式串在文本串中的起始位置）。
  • 总结
    • KMP算法通过预处理模式串构建next数组，利用匹配失败时的已知信息跳过不必要的比较，显著提高了字符串匹配的效率。其核心在于next数组的计算和匹配时的回退策略，适用于需要频繁匹配的场景。

代码实现

// KMP算法模版
// 测试链接 : https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
public class Code01_KMP {

    public static int strStr(String s1, String s2) {
        // return s1.indexOf(s2);
        return kmp(s1.toCharArray(), s2.toCharArray());
    }

    // KMP算法
    public static int kmp(char[] s1, char[] s2) {
        // s1中当前比对的位置是x
        // s2中当前比对的位置是y
        int n = s1.length, m = s2.length, x = 0, y = 0;
        // O(m)
        int[] next = nextArray(s2, m);
        // O(n)
        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;
    }

    // 得到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;
        // i表示当前要求next值的位置
        // cn表示当前要和前一个字符比对的下标
        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;
    }

}

二.另一棵树的子树

题目：另一棵树的子树

算法原理

  • 方法1：暴力递归
    • 整体原理：
      • 遍历主树t1的每一个节点，检查以该节点为根的子树是否与t2完全相同。
      • 如果t1的当前节点与t2的根节点值相同，则递归检查左右子树是否相同。
      • 如果不同，则递归检查t1的左子树或右子树是否包含t2。
    • 具体步骤：
      • 如果t1和t2都非空：
        • 检查t1当前子树是否与t2相同（same(t1, t2)）。
        • 如果不相同，递归检查t1的左子树或右子树是否包含t2。
      • 如果t2为空，则返回true（空树是任何树的子树）。
      • 否则返回false。
    • 复杂度分析：
      • 时间复杂度：O(n * m)，其中n是t1的节点数，m是t2的节点数。最坏情况下需要遍历t1的每个节点，并对每个节点检查t2。
      • 空间复杂度：O(max(n, m))，递归栈的深度取决于树的高度。
    • 示例：
      • t1：
      •       3
     / \
    4   5
   / \
  1   2

      • t2：
      •     4 
   / \
  1   2

      • 检查t1的根节点3，不匹配。
      • 检查左子树4，匹配t2的根节点4，递归检查左右子树，完全匹配，返回true。
  • 方法2：先序序列化 + KMP
    • 整体原理：
      • 将t1和t2先序序列化为字符串列表（包括null表示空节点）。
      • 使用KMP算法检查t2的序列化结果是否是t1的子串。
    • 具体步骤：
      • 序列化：
        • 递归遍历树，将节点值（或null）加入列表。
        • 例如，t1序列化为[3, 4, 1, null, null, 2, null, null, 5, null, null]。
        • t2序列化为[4, 1, null, null, 2, null, null]。
      • KMP匹配：
        • 构建t2的next数组（最长相同前后缀）。
        • 在t1的序列化列表中匹配t2的序列化列表。
    • 复杂度分析：
      • 时间复杂度：O(n + m)，序列化时间为O(n + m)，KMP匹配时间为O(n + m)。
      • 空间复杂度：O(n + m)，存储序列化结果和next数组。
    • 示例：
      • t1序列化：[3, 4, 1, null, null, 2, null, null, 5, null, null]。
      • t2序列化：[4, 1, null, null, 2, null, null]。
      • KMP在t1的列表中找到t2的子串，返回true。
    • 总结
      • 暴力递归：直观但效率低，适合小规模数据。
      • 序列化 + KMP：高效，适合大规模数据，利用字符串匹配优化。 选择依据：根据数据规模选择方法，优先推荐方法2。

代码实现

import java.util.ArrayList;

// 另一棵树的子树
// 给你两棵二叉树root和subRoot
// 检验root中是否包含和subRoot具有相同结构和节点值的子树
// 如果存在，返回true
// 否则，返回false
// 测试链接 : https://leetcode.cn/problems/subtree-of-another-tree/
public class Code02_SubtreeOfAnotherTree {

    // 不要提交这个类
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    // 方法1
    // 暴力递归
    // 时间复杂度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);
        }
        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;
    }

    // 方法2
    // 二叉树先序序列化 + 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;
        }
        return t2 == null;
    }

    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);
        }
    }

    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))) {
                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 < next.length) {
            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;
    }

    // 比对两个字符串是否相等
    // a和b可能为null
    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;
    }

}

# 算法 # java # 数据结构
Logo
EazyDevelop社区

一站式 AI 云服务平台

更多推荐

cover

2026 跨端协作远控深度横评——功能齐全度实测对比，附评分表与选型建议（开发者实测）

avatar EazyDevelop社区
cover

[Grok Bot 仓颉实践] 让 AI 助手替你干活之前，先想清楚谁来拍板——我用 Grok Bot 做游戏的做法

avatar EazyDevelop社区
cover

Excel按照某一列分类输出各个表格：不会VBA、不装Python，三步拆完

avatar EazyDevelop社区