从一道简单题入手,向你介绍 KMP 算法|Java 刷题打卡

简介: 从一道简单题入手,向你介绍 KMP 算法|Java 刷题打卡

题目描述



这是 LeetCode 上的 28. 实现 strStr() ,难度为 简单


Tag : 「子串匹配」、「KMP」


实现 strStr() 函数。


给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。


如果不存在,则返回  -1 。


说明:


  • 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
  • 对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。


示例 1:


输入:haystack = "hello", needle = "ll"
输出:2
复制代码


示例 2:


输入:haystack = "aaaaa", needle = "bba"
输出:-1
复制代码


示例 3:


输入:haystack = "", needle = ""
输出:0
复制代码


提示:


  • 0 <= haystack.length, needle.length <= 5 * 10410^4104
  • haystack 和 needle 仅由小写英文字符组成


朴素解法



直观的解法的是:枚举原串 ss 中的每个字符作为「发起点」,每次从原串的「发起点」和匹配串的「首位」开始尝试匹配:


  • 匹配成功:返回本次匹配的原串「发起点」。
  • 匹配失败:枚举原串的下一个「发起点」,重新尝试匹配。


代码:


class Solution {
    public int strStr(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始,尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配,返回原串的「发起点」下标
            if (b == m) return i;
        }
        return -1;
    }
}
复制代码


  • 时间复杂度:n 为原串的长度,m 为匹配串的长度。其中枚举的复杂度为 O(n−m)O(n - m)O(nm),构造和比较字符串的复杂度为 O(m)O(m)O(m)。整体复杂度为 O((n−m)∗m)O((n - m) * m)O((nm)m)
  • 空间复杂度:O(1)O(1)O(1)


KMP 解法



KMP 算法是一个快速查找匹配串的算法,它的作用其实就是本题问题:如何快速在「原字符串」中找到「匹配字符串」。


上述的朴素解法,不考虑剪枝的话复杂度是 O(m∗n)O(m * n)O(mn) 的,而 KMP 算法的复杂度为 O(m+n)O(m + n)O(m+n)


KMP 之所以能够在 O(m+n)O(m + n)O(m+n) 复杂度内完成查找,是因为其能在「非完全匹配」的过程中提取到有效信息进行复用,以减少「重复匹配」的消耗。


你可能不太理解,没关系,我们可以通过举 🌰 来理解 KMP。


1. 匹配过程


在模拟 KMP 匹配过程之前,我们先建立两个概念:


  • 前缀:对于字符串 abcxxxxefg,我们称 abc 属于 abcxxxxefg 的某个前缀。
  • 后缀:对于字符串 abcxxxxefg,我们称 efg 属于 abcxxxxefg 的某个后缀。


然后我们假设原串为 abeababeabf,匹配串为 abeabf


网络异常,图片无法展示
|


我们可以先看看如果不使用 KMP,会如何进行匹配(不使用 substring 函数的情况下)。


首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置。


首次匹配的「发起点」是第一个字符 a。显然,后面的 abeab 都是匹配的,两个指针会同时往右移动(黑标)。


在都能匹配上 abeab 的部分,「朴素匹配」和「KMP」并无不同。


直到出现第一个不同的位置(红标):


网络异常,图片无法展示
|


接下来,正是「朴素匹配」和「KMP」出现不同的地方:


  • 先看下「朴素匹配」逻辑:


1. 将原串的指针移动至本次「发起点」的下一个位置(b 字符处);匹配串的指针移动至起始位置。

2. 尝试匹配,发现对不上,原串的指针会一直往后移动,直到能够与匹配串对上位置。


如图:


网络异常,图片无法展示
|


也就是说,对于「朴素匹配」而言,一旦匹配失败,将会将原串指针调整至下一个「发起点」,匹配串的指针调整至起始位置,然后重新尝试匹配。


这也就不难理解为什么「朴素匹配」的复杂度是 O(m∗n)O(m * n)O(mn) 了。


  • 然后我们再看看「KMP 匹配」过程:


首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在,则跳转到「前缀」的下一个位置继续往下匹配:


网络异常,图片无法展示
|


跳转到下一匹配位置后,尝试匹配,发现两个指针的字符对不上,并且此时匹配串指针前面不存在相同的「前缀」和「后缀」,这时候只能回到匹配串的起始位置重新开始:


网络异常,图片无法展示
|


到这里,你应该清楚 KMP 为什么相比于朴素解法更快:


  • 因为 KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配。
  • 因为 KMP 的原串指针不会进行回溯(没有朴素匹配中回到下一个「发起点」的过程)。


第一点很直观,也很好理解。


我们可以把重点放在第二点上,原串不回溯至「发起点」意味着什么?


其实是意味着:随着匹配过程的进行,原串指针的不断右移,我们本质上是在不断地在否决一些「不可能」的方案。


当我们的原串指针从 i 位置后移到 j 位置,不仅仅代表着「原串」下标范围为 [i,j)[i,j)[i,j) 的字符与「匹配串」匹配或者不匹配,更是在否决那些以「原串」下标范围为 [i,j)[i,j)[i,j) 为「匹配发起点」的子集。


2. 分析实现


到这里,就结束了吗?要开始动手实现上述匹配过程了吗?


我们可以先分析一下复杂度。如果严格按照上述解法的话,最坏情况下我们需要扫描整个原串,复杂度为 O(n)O(n)O(n)。同时在每一次匹配失败时,去检查已匹配部分的相同「前缀」和「后缀」,跳转到相应的位置,如果不匹配则再检查前面部分是否有相同「前缀」和「后缀」,再跳转到相应的位置 ... 这部分的复杂度是 O(m2)O(m^2)O(m2) ,因此整体的复杂度是 O(n∗m2)O(n * m^2)O(nm2),而我们的朴素解法是 O(m∗n)O(m * n)O(mn) 的。


说明还有一些性质我们没有利用到。


显然,扫描完整原串操作这一操作是不可避免的,我们可以优化的只能是「检查已匹配部分的相同前缀和后缀」这一过程。


再进一步,我们检查「前缀」和「后缀」的目的其实是「为了确定匹配串中的下一段开始匹配的位置」。


同时我们发现,对于匹配串的任意一个位置而言,由该位置发起的下一个匹配点位置其实与原串无关。


举个 🌰,对于匹配串 abcabd 的字符 d 而言,由它发起的下一个匹配点跳转必然是字符 c 的位置。因为字符 d 位置的相同「前缀」和「后缀」字符 ab 的下一位置就是字符 c


可见从匹配串某个位置跳转下一个匹配位置这一过程是与原串无关的,我们将这一过程称为找 next 点。


显然我们可以预处理出 next 数组,数组中每个位置的值就是该下标应该跳转的目标位置( next 点)。


当我们进行了这一步优化之后,复杂度是多少呢?


预处理 next 数组的复杂度未知,匹配过程最多扫描完整个原串,复杂度为 O(n)O(n)O(n)


因此如果我们希望整个 KMP 过程是 O(m+n)O(m + n)O(m+n) 的话,那么我们需要在 O(m)O(m)O(m) 的复杂度内预处理出 next数组。


所以我们的重点在于如何在 O(m)O(m)O(m) 复杂度内处理处 next 数组。


3. next 数组的构建


接下来,我们看看 next 数组是如何在 O(m)O(m)O(m) 的复杂度内被预处理出来的。

假设有匹配串 aaabbab,我们来看看对应的 next 是如何被构建出来的。


网络异常,图片无法展示
|

网络异常,图片无法展示
|

网络异常,图片无法展示
|

网络异常,图片无法展示
|


这就是整个 next 数组的构建过程,时空复杂度均为 O(m)O(m)O(m)


至此整个 KMP 匹配过程复杂度是 O(m+n)O(m + n)O(m+n) 的。


4. 代码实现


在实际编码时,通常我会往原串和匹配串头部追加一个空格(哨兵)。


目的是让 j 下标从 0 开始,省去 j-1 开始的麻烦。


整个过程与上述分析完全一致,一些相关的注释我已经写到代码里。


代码:


class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格,使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        // 构建 next 数组,数组长度为匹配串的长度(next 数组是和匹配串相关的)
        int[] next = new int[m + 1];
        // 构造过程 i = 2,j = 0 开始,i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话,j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话,先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i],结束本次循环,i++
            next[i] = j;
        }
        // 匹配过程,i = 1,j = 0 开始,i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话,先让 j++,结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功,直接返回下标
            if (j == m) return i - m;
        }
        return -1;
    }
}
复制代码


  • 时间复杂度:n 为原串的长度,m 为匹配串的长度。复杂度为 O(m+n)O(m + n)O(m+n)
  • 空间复杂度:构建了 next 数组。复杂度为 O(m)O(m)O(m)


总结



KMP 算法的应用范围要比 Manacher 算法广,Manacher 算法只能应用于「回文串」问题,相对比较局限,而「子串匹配」问题还是十分常见的。


背过这样的算法的意义在于:相当于大脑里有了一个时间复杂度为 O(n)O(n)O(n) 的 api 可以使用,这个 api 传入一个原串和匹配串,返回匹配串在原串的位置。


因此,三叶十分建议大家在「理解 KMP」的基础上,对模板进行背过 ~


最后



这是我们「刷穿 LeetCode」系列文章的第 No.28 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
3月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
76 0
|
3月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
116 1
|
4月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
351 58
|
4月前
|
机器学习/深度学习 监控 算法
局域网行为监控软件 C# 多线程数据包捕获算法:基于 KMP 模式匹配的内容分析优化方案探索
本文探讨了一种结合KMP算法的多线程数据包捕获与分析方案,用于局域网行为监控。通过C#实现,该系统可高效检测敏感内容、管理URL访问、分析协议及审计日志。实验表明,相较于传统算法,KMP在处理大规模网络流量时效率显著提升。未来可在算法优化、多模式匹配及机器学习等领域进一步研究。
115 0
|
5月前
|
存储 机器学习/深度学习 算法
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty  敏感词
|
5月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
206 0
|
5月前
|
存储 缓存 监控
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
109 3
|
5月前
|
负载均衡 算法 关系型数据库
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
|
6月前
|
存储 机器学习/深度学习 监控
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
138 3
|
8月前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。

热门文章

最新文章