从 KMP算法到 Java的 String.indexOf(String str)方法

简介: 从 KMP算法到 Java的 String.indexOf(String str)方法

一、前言

从九月一开始日刷算法,每日三题稳定收获 LeetCode 21积分,在今天刷到 28. 实现 strStr()时, 最开始使用了暴力破解,双重循环(下面有具体介绍),但是在我看评论区的时候,发现这道题是 KMP的经典题目,但是我连什么是 KMP都不知道,接下来我会为和我一样的算法小白分享一下我理解的 KMP算法和相关题目的讲解

二、LeetCode 28. 实现 strStr()

题目描述

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

解题思路(暴力破解)

  • 根据文中所说,在字符串 haystack中找出 needle,找到了就返回第一个字符串出现位置的下标
  • 这个时候,我灵机一动,这不就是两层循环的事情吗,第一层循环遍历 haystack,然后第二次循环遍历 needle,判断字符串是否相等就可以了
  • 于是我开始对字符串下手了,先将两个字符串都转为数组
  • 第一层 for循环从下标 0开始,终止条件是 haystack的长度
  • 第二个 while循环的开始条件是当前外层循环的字符 == needle的第一个字符
  • 相等 i++,n++
  • 不相等 结束 while循环
  • 每次在去判断一下 n是否 == needle的长度
  • 相等则表明 needle在字符串 haystack中

假设目标字符串 haystack为 abcabde,needle字符串为 abd

下图为暴力破解的流程图

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

代码实现

public static int strStr(String haystack, String needle) {
    // 字符串转为 char数组
    char[] chars = haystack.toCharArray();
    char[] chars1 = needle.toCharArray();
    // 遍历字符串 haystack
    for (int i = 0; i < chars.length; i++) {
        // n表示第二层for循环的数组下标, m表示第一层for循环的数组下标
        int n = 0;
        int m = i;
        // 遍历 needle对应的 char数组,判断 chars[m] == chars1[n]
        while(m < chars.length && n < chars1.length && chars[m] == chars1[n]){
            m++;
            n++;
        }
        // 判断遍历的第二个字符串 needle的数组是否遍历完成
        // 只有 needle包含在 haystack中,才能使得 n == chars.length
        if (n == chars1.length && chars[m - 1] == chars1[n - 1]){
            return i;
        }
    }
    return -1;
}
复制代码

提交结果

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

小题总结

我知道自己的方法属于暴力破解,正确方式不应该这样做,所以我看了评论区和题解区发现有以下几种题解方式

  • 使用 String.substring(int beginIndex, int endIndex)方法截取字符串的
  • 内置函数(方法), 例如: String.indexOf(String str)
  • 像我一样两层循环
  • 双指针
  • KMP

看到 KMP的时候我真的是懵的,因为听都没听说过,在看下面的评论,差点吓退我,但是 内卷人是这么容易被吓退的吗?赶紧学起来

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

三、KMP算法

由来

外国人: Knuth,Morris和Pratt发明了这个算法,然后取它三个的首字母进行了命名。所以叫做KMP

用处

主要应用在 字符串匹配中

最长公共前后缀

将字符串拆分成以首字符开始的各个子串,然后依次判断,下标 n与下标 length - n - 1的元素是否相等,若有 m个连续相等的字符,则最长公共前缀为 m

例如字符串:AABAAF的公共前后缀长度如下图所示,红色代表不相同,蓝色代表元素相同

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

知道了公共前缀, 相应的可以利用我们获取到的公共前缀表来找到当字符不匹配的时候指针应该移动的位置,如下图所示:

下图来自于 代码随想录

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

核心:next数组

next数组就是用来存储公共前缀的个数的, 例如上面的例子,他的next数组结果就应该是

int[] next = {0,1,0,1,2,0}
复制代码

思路分析

  • 前置条件, 字符串 s,前缀数组 int[] next
  • 设置一个整数 j代表最长公共前后缀的个数
  • 首先是初始化,我们的 next数组第一个元素肯定是 0
  • 然后去 for循环我们的字符串,这里需要注意的是我们的for循环是从下标 1开始的
  • 判断 j必须大于 0不然的话在回溯过程中会发生 越界的情况,还要判断元素是否相等
  • 若不相等则 j回溯到上一个 next数组下标
  • 这里需要注意的是要用 while循环,因为可能会一直进行回溯操作
  • 当 s.charAt(j) == s.charAt(i)时,代表最长前后缀元素个数 +1,所以 j++
  • 最后将 j的值赋给数组 next[i]

代码展示

public static int[] getNext(String s,int[] next){
    int j = 0;
    // 初始化下标 0
    next[0] = 0;
    for (int i = 1; i < s.length(); i++) {
        while(j > 0 && s.charAt(j) != s.charAt(i)){
            j = next[j - 1];
        }
        if (s.charAt(j) == s.charAt(i)){
            j++;
        }
        next[i] = j;
    }
    return next;
}
复制代码

四、LeetCode 28. 实现 strStr()

现在我们重新根据 KMP算法来做一遍 LeetCode 28题

思路分析

  • 判断 needle长度是否等于 0,如果等于 0则返回 0
  • 判断 needle长度是否大于 haystack,如果大于则返回 -1
  • 创建 next数组
  • 执行我们的 getNext方法
  • 设置 next数组的指针 j = 0
  • for循环遍历 haystack
  • next指针大于 0时判断字符串 haystack下标 i位置的元素是否等于字符串 needle下标 j的位置
  • 不相等则 j进行回溯操作
  • 一样的, 回溯可能多次,所以使用 while循环
  • 如果相等
  • j++
  • 如果 j == needle的长度,则代表 haystack包含字符串 needle
  • 返回 i - j + 1;

代码展示

public static int strStr2(String haystack, String needle) {
        // 如果 needle为 “” 则返回0
        if (needle.length() == 0){
            return 0;
        }
        // 如果 needle的长度大于 haystack则返回 -1
        if (needle.length() > haystack.length()){
            return -1;
        }
        // 生成 next数组
        int[] next = new int[needle.length()];
        getNext(needle,next);
        // 标记指针在 needle回退后的位置
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            // 判断当前位置
            while(j > 0  && haystack.charAt(i) != needle.charAt(j)){
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)){
                j++;
            }
            if (j == needle.length()){
                return i - j + 1;
            }
        }
        return -1;
    }
    public static int[] getNext(String s,int[] next){
        int j = 0;
        // 初始化下标 0
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while(j > 0 && s.charAt(j) != s.charAt(i)){
                j = next[j - 1];
            }
            if (s.charAt(j) == s.charAt(i)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
复制代码

提交结果

虽然但是,没有暴力破解的速度快,但是确实也学到了一种算法

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

五、String.index(String str)

在 LeetCode评论区有人直接使用了编程语言封装好的方法或者函数,我以前也只是使用过,接下来我们一起看一下源代码

我使用的测试代码如下所示

String haystack = "mississippi", needle = "issip";
int i1 = haystack.indexOf(needle);
复制代码

对应的源码方法重载跳转如下所示:

  • 先进入 indexOf(String str)方法
  • 跳转进入 indexOf(String str, int fromIndex)
  • 这个时候 fromIndex == 0
  • 跳转进入 inexOf(char[] source, int sourceOffset, int sourceCount,            char[] target, int targetOffset, int targetCount,            int fromIndex)
  • value表示 haystack元素的 char数组
  • value.length表示 haystack的长度
  • str.value表示 needle元素的 char数组
  • str.value.length表示 needle的长度
  • 接下来我们看 indexOf方法的具体实现

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

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

String.indexOf()方法详解

因为我没有下载 java8源码,所以直接在这里进行注释标注了

// source:       当前字符串元素
// sourceOffset: 偏移量
// sourceCount: 当前字符串长度
// target:      目标字符串
// targetOffset:目标字符串偏移量
// targetCount: 目标字符串长度
// fromIndex:   索引位置
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    if (fromIndex < 0) {
        fromIndex = 0;
    }
    // 如果目标字符串的长度为 0则直接返回 索引位置 (我们这里因为之前方法重载 fromIndex为 0 所以返回 0)
    if (targetCount == 0) {
        return fromIndex;
    }
    // 获取目标 首字符
    char first = target[targetOffset];
    // 我们这里就是 源字符串长度 - 目标字符串长度, sourceOffset == 0
    int max = sourceOffset + (sourceCount - targetCount);
    // 循环,i == 0
    // 加入循环到了 max的索引位置还没有找到和 目标字符串首字符相等的元素,则源字符串中肯定不包含目标字符串
    for (int i = sourceOffset + fromIndex; i <= max; i++) {
        // 搜索首字符所在位置
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }
        // 找到了首字符,判断其余字符位置是否相等
        if (i <= max) {
            int j = i + 1;
            // 根据目标字符串的长度截取源字符串从下标 i开始相同长度的字符串
            int end = j + targetCount - 1;
            // 遍历判断
            for (int k = targetOffset + 1; j < end && source[j]
                    == target[k]; j++, k++);
            // 如果到最后一个元素都相同,则代表源字符串内包含目标字符串
            if (j == end) {
                // 这里就直接返回了 i 因为源字符串偏移量为 0
                return i - sourceOffset;
            }
        }
    }
    return -1;
}
复制代码

使用该源码方式做 LeetCode 28题

public static int strStr(String haystack, String needle) {
    // 如果 needle为 “” 则返回0
    if (needle.length() == 0){
        return 0;
    }
    // 如果 needle的长度大于 haystack则返回 -1
    if (needle.length() > haystack.length()){
        return -1;
    }
    int max = haystack.length() - needle.length();
    char first = needle.charAt(0);
    for (int i = 0; i <= max; i++) {
        if (haystack.charAt(i) != first){
            while(++i <= max && haystack.charAt(i) != first);
        }
        if (i <= max) {
            int j = i + 1;
            int end = j + needle.length() - 1;
            for (int k = 1; j < end && haystack.charAt(j)
                    == needle.charAt(k); j++, k++);
            if (j == end) {
                return i ;
            }
        }
    }
    return -1;
}
复制代码

提交结果

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

六、后续

KMP真的很难理解,建议多看几遍 B站代码随想录,文章也的再好,我感觉也没有视频来的直观,更何况我还是一个初级作者(脸上贴金ing)

接下来,还有一道题 LeetCode 459. 重复的子字符串也可以使用 KMP算法进行解答,感兴趣的可以关注一下我的专栏每日算法

由于算法方面特别影响推荐,我还准备去记录一下自己的刷题,所以每周更新一次算法刷题进度和思路分析,每天三道没有做过的题目,欢迎大家关注



目录
相关文章
|
1月前
|
存储 算法 安全
探究‘公司禁用 U 盘’背后的哈希表算法与 Java 实现
在数字化办公时代,信息安全至关重要。许多公司采取“禁用U盘”策略,利用哈希表算法高效管理外接设备的接入权限。哈希表通过哈希函数将设备标识映射到数组索引,快速判断U盘是否授权。例如,公司预先将允许的U盘标识存入哈希表,新设备接入时迅速验证,未授权则禁止传输并报警。这有效防止恶意软件和数据泄露,保障企业信息安全。 代码示例展示了如何用Java实现简单的哈希表,模拟公司U盘管控场景。哈希表不仅用于设备管理,还在文件索引、用户权限等多方面助力信息安全防线的构建,为企业数字化进程保驾护航。
|
2月前
|
监控 算法 网络协议
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
81 15
|
23天前
|
存储 Java 索引
Java快速入门之数组、方法
### Java快速入门之数组与方法简介 #### 一、数组 数组是一种容器,用于存储同种数据类型的多个值。定义数组时需指定数据类型,如`int[]`只能存储整数。数组的初始化分为静态和动态两种: - **静态初始化**:直接指定元素,系统自动计算长度,如`int[] arr = {1, 2, 3};` - **动态初始化**:手动指定长度,系统给定默认值,如`int[] arr = new int[3];` 数组访问通过索引完成,索引从0开始,最大索引为`数组.length - 1`。遍历数组常用`for`循环。常见操作包括求和、找最值、统计特定条件元素等。
|
5天前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
19天前
|
Java
Java快速入门之类、对象、方法
本文简要介绍了Java快速入门中的类、对象和方法。首先,解释了类和对象的概念,类是对象的抽象,对象是类的具体实例。接着,阐述了类的定义和组成,包括属性和行为,并展示了如何创建和使用对象。然后,讨论了成员变量与局部变量的区别,强调了封装的重要性,通过`private`关键字隐藏数据并提供`get/set`方法访问。最后,介绍了构造方法的定义和重载,以及标准类的制作规范,帮助初学者理解如何构建完整的Java类。
|
17天前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
19天前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
58 16
|
16天前
|
Java 程序员 调度
Java 高级面试技巧:yield() 与 sleep() 方法的使用场景和区别
本文详细解析了 Java 中 `Thread` 类的 `yield()` 和 `sleep()` 方法,解释了它们的作用、区别及为什么是静态方法。`yield()` 让当前线程释放 CPU 时间片,给其他同等优先级线程运行机会,但不保证暂停;`sleep()` 则让线程进入休眠状态,指定时间后继续执行。两者都是静态方法,因为它们影响线程调度机制而非单一线程行为。这些知识点在面试中常被提及,掌握它们有助于更好地应对多线程编程问题。
50 9
|
1月前
|
机器学习/深度学习 人工智能 算法
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
207 13
机器学习算法的优化与改进:提升模型性能的策略与方法
|
1月前
|
运维 监控 算法
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
64 32