14409 字
约 48 分钟
6
028.实现 strStr()
2026-09-19
数据结构与算法
无标签

028.实现 strStr()

作者：沉默王二
发布时间：2024-02-19T08:00:07.673+0800

鲁迅说过，春节过后，依然要加强学习，不断提高自己。每天一道二哥的 LeetCode 刷题笔记，精神百倍。先用 String 的 indexOf() 方法实现方式来 strStr() 方法，然后再用 KMP 算法来实现一遍，酸爽极了。

开工好多事情要做，忙不过来了，简历要修改，LeetCode 要刷，MySQL 教程要搞，新的项目要启动，但忙碌的感觉还真的挺好，至少让我感觉是积极的。技术派阅读地址：https://paicoding.com/column/7/28

  • 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

  • 这道题可以说完全重写了，给出 3 道大家完全都能掌握的题解（String 的 indexOf、substring+equals+for 循环、KMP 算法）。

  • 增加代码注释，这样大家更容易看懂并掌握题解；

  • 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

  • 增加手绘图，这样大家更容易理解解题思路；

  • 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

  • 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

  • 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

  • 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

难度

简单

示例

例 1

输入：haystack = "sadbutsad", needle = "sad"

解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。

例 2

输入：haystack = "leetcode", needle = "leeto"

解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

分析 1

对于这道题，我们很容易想到 **Java 字符串 **的indexOf()方法，我在二哥的 Java 进阶之路上也帮大家讲过这个方法的实现。

那题解立马就有了，嘿嘿 😜。

class Solution {

    int index = haystack.indexOf(needle);        return index;    }}

并且题解效率非常高：

直接就击败 100% 的 Java 用户。

分析 2

不过 LeetCode 出这道题，显然不是为了让我们直接调用indexOf()方法，而是让我们去实现一个indexOf()方法。

既然如此，我们不妨再来看一下 indexOf 方法的源码（最终 indexOf(String str) 调用的方法）：

JDK8 版本的方法签名是：

static int indexOf(char[] source, int sourceOffset, int sourceCount,

        int fromIndex)

先来看参数：

  • source：主字符串的字符数组。
  • sourceOffset：主字符串的起始偏移量。
  • sourceCount：主字符串中字符的总数。
  • target：要查找的子字符串的字符数组。
  • targetOffset：子字符串的起始偏移量。
  • targetCount：子字符串中字符的总数。
  • fromIndex：开始搜索的索引位置。

再来看逻辑流程：

  • 首先，检查fromIndex是否大于或等于sourceCount。如果是，且targetCount为 0，则返回sourceCount；否则返回-1。
  • 如果fromIndex小于 0，它被设置为 0。
  • 如果targetCount为 0，则直接返回fromIndex，因为空字符串被认为存在于任何位置。
  • 然后，计算最大搜索索引max，这是为了确保搜索时target能够完全位于source中。
  • 接下来，遍历source数组，从sourceOffset + fromIndex开始，直到max，查找与target数组中第一个字符匹配的字符。
  • 一旦找到第一个匹配的字符，就在source中从这个位置开始，尝试匹配整个target数组。
  • 如果所有后续字符都匹配，就返回当前的索引（调整过的，即i - sourceOffset），因为这表示找到了完整的子字符串。
  • 如果遍历完成后未找到匹配的子字符串，则返回-1。

这种实现方式在处理大字符串时效率不如KMP（Knuth-Morris-Pratt）算法，但 JDK 选择了这种更易于理解和实现的方法，足以处理大多数常见的情况。

所以，我们可以按照这个思路来实现我们的strStr()方法。

class Solution {

    // 获取主字符串和子字符串的长度        int sourceCount = haystack.length();        int targetCount = needle.length();                // 如果子字符串为空，则根据题目要求返回0        if (targetCount == 0) {            return 0;        }                // 获取子字符串的第一个字符，用于后续匹配的起点        char first = needle.charAt(0);        // 计算搜索的最大起始位置，确保子字符串能够完全位于主字符串中        int max = sourceCount - targetCount;                // 遍历主字符串        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 + targetCount - 1; // 计算子字符串在主字符串中的结束位置                for (int k = 1; j < end && haystack.charAt(j) == needle.charAt(k); j++, k++);                // 如果整个子字符串都匹配了，返回其在主字符串中的起始索引                if (j == end) {                    return i;                }            }        }        // 如果遍历完成后没有找到匹配的子字符串，返回-1        return -1;    }}

如果觉得上面的代码有点复杂，我们可以稍微简化一下：

class Solution {

    // 如果 needle 是空字符串，则按照题目要求返回 0        if (needle.isEmpty()) {            return 0;        }        // 获取两个字符串的长度        int n = haystack.length();        int m = needle.length();        // 遍历 haystack 字符串        for (int i = 0; i <= n - m; i++) {            // 从 haystack 的第 i 个字符开始，取一个长度为 m 的子字符串            String subStr = haystack.substring(i, i + m);            // 比较这个子字符串与 needle 是否相等            if (subStr.equals(needle)) {                return i; // 如果相等，则返回当前的起始位置            }        }        return -1; // 如果遍历结束都没有找到匹配的位置，则返回 -1    }}

这个方法就非常好懂了，对吧，我们只需要遍历主字符串，然后取出一个长度为子字符串的子串，然后比较两个子串是否相等，如果相等，就返回当前的起始位置。

利用了字符串的 substring() 方法和 equals() 方法，来看一下题解效率：

也非常的高，同样击败了 100% 的 Java 用户。针对这道题，掌握这种方法将就足够了。

分析 3

这里顺带讲一下 KMP 算法，可能有些**球友 **需要。

先让我们从最朴素的暴力算法开始！

假如 haystack = "hello", needle = "ll"，匹配步骤如下图所示：

这样子就能实现较为简单的字符串匹配了，时间复杂度为 ，n 代表原串的长度，m 代表匹配串的长度。

其实分析 2 中的题解就是用的这种思路。

但这样会存在一个问题，当字符串长度非常非常长的时候……这个思路的时间复杂度就不太理想了。

再来看下面这个例子，假如 haystack = "abbacabbab", needle = "abbab"，匹配步骤如下图所示：

这种方式能匹配，但是，不够好！

因为每次匹配失败，匹配串的下标都要回到开头（也就是重新从 needle[0]开始），并且原串的下标也要往回移动（从 haystack[i+1]开始），真的需要这么麻烦吗？

其实真不用，因为匹配串的开头有个ab（字符 b 的前缀），和结尾的ab（字符 b 的后缀）是一样的。

如果匹配串abbab在最后一个位置和原串匹配失败了，那么原串前面肯定存在abba，因为匹配串是以abba开头的，这时候我们要移动的话，就可以保持原串的下标不变（也就是下图中箭头指向的“c”的位置 haystack[4]）然后让匹配串直接从第一个a的位置开始往后匹配，移动匹配串的下标见下图：

这样子是不是就省去了一部分比较的步骤呢？为什么可以这样做呢？

这就不得不说一说 KMP 算法了。

KMP算法是由 Knuth、Pratt 和 Morris 在 1977 年共同发布的，用来解决字符串匹配问题的算法。

KMP 算法核心思想概括成一句话就是 利用已经匹配过的残余信息，使原串的比较位置保持不变，而匹配串的比较位置尽快移动到有效的地方。

回顾之前的暴力步骤，如果从 haystack[i] 开始的那一趟比较失败了，算法会尝试从 haystack[i+1] 开始比较。这种行为，属于典型的“没有从之前的错误中学到东西”。

我们应当注意到，一次失败的匹配，会给我们提供宝贵的信息——再次观察暴力算法中的移动方法，匹配串abbab在第一次匹配失败后，我们应该如何移动原串和匹配串的下标呢？

答案见下图，原创的位置保持不变，只需要移动匹配串到第二个 b 的位置就可以了。因为以最后一个位置的 b 结尾的后缀，最多能与前缀ab匹配。

也就是图中的蓝色部分与绿色部分相匹配。

所以……在匹配失败之后，我们能够让匹配串的比较位置以最快的速度移动到的位置，就是——以 当前比较位置结尾的能够匹配的最长前缀 ！！

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

到这里，我们应该清楚 KMP 为什么相比于暴力解法更快：

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

前缀和后缀又是怎么求出来的呢？

这就涉及到了 KMP 算法 的next[]数组，它就是匹配串位置能移动到的有效的且最远的位置。

next[]数组到底要怎么求呢？我们显然不能挨个去对每个前缀后缀处理，因为这样子时间开销太大了！

其实只需要匹配串对自身 匹配 一次就可以得出了。

class GetNext{

public void getNext(String p, int[] next) {        // next数组的第一个元素总是-1，这是KMP算法的约定，表示不存在更短的相同前缀和后缀        next[0] = -1;                // posK表示前缀的最后一个字符位置，posJ表示后缀的最后一个字符位置        int posK = -1, posJ = 0;                // 遍历模式字符串p来计算每个位置的next值        while (posJ < p.length() - 1) { // 注意这里posJ < p.length() - 1，因为next数组的最后一个值是不需要计算的            // 当posK为-1时，表示我们需要从头开始匹配或者p.charAt(posK) == p.charAt(posJ)，即当前字符匹配成功            if (posK == -1 || p.charAt(posK) == p.charAt(posJ)) {                posJ++;                posK++;                // 设置next数组的值。此时，posK也表示posJ位置字符之前的p子串中，前缀和后缀最长公共元素的长度                next[posJ] = posK;            } else {                // 如果匹配失败，则根据next数组回溯。即，让posK回到上一个可能匹配的位置                posK = next[posK];            }        }    }}

上述代码中，我们用posJ和posK来求解next[]数组，我们来模拟一遍。

posK就相当于对匹配串自己 匹配 的一个变量，只不过它是后缀来匹配前缀，这样子我们就求解出了next[]数组，然后只需要按照next[]数组的值，在匹配串与原串失配的时候，把匹配串的位置相应的移动即可。

这次，我们再来用next[]数组来优化我们的字符串匹配过程和之前朴素想法一对比……：

是不是节省了很大一部分，而在数据规模越大的情况下，我们能够优化的也就越多！

class Solution {

private void getNext(String p, int[] next) {        next[0] = -1; // 初始化next数组的第一个值为-1        int posK = -1, posJ = 0; // posK和posJ分别表示前缀和后缀的比较位置                // 遍历模式字符串p来计算next数组的值        while (posJ < p.length() - 1) {            // 如果posK为-1，或当前字符匹配成功，则向前移动posK和posJ            if (posK == -1 || p.charAt(posK) == p.charAt(posJ)) {                posJ++;                posK++;                next[posJ] = posK; // 更新next数组            } else {                // 如果当前字符匹配失败，根据next数组回溯posK                posK = next[posK];            }        }    }        // strStr方法实现了KMP算法来找出needle在haystack中的第一次出现的位置    public int strStr(String haystack, String needle) {        if (needle.isEmpty()) return 0; // 特殊情况处理：空字符串                int[] next = new int[needle.length() + 1]; // 初始化next数组        getNext(needle, next); // 调用getNext方法填充next数组                int posI = 0, posJ = 0; // posI和posJ分别表示在haystack和needle中的当前位置                // 在haystack中遍历，尝试匹配needle        while (posI < haystack.length() && posJ < needle.length()) {            // 如果posJ为-1（即需要从头开始匹配）或当前字符匹配成功            if (posJ == -1 || haystack.charAt(posI) == needle.charAt(posJ)) {                posI++;                posJ++;            } else {                // 如果当前字符匹配失败，根据next数组回溯posJ                posJ = next[posJ];            }        }                // 如果完全匹配，返回匹配的起始位置        if (posJ == needle.length()) return posI - posJ;        // 如果匹配失败，返回-1        return -1;    }}

时间复杂度：

我们利用 已经匹配过的信息 来对匹配失败的地方进行处理，不断调整匹配串的位置，时间复杂度就得到了优化。

但 LeetCode 测出来的效果其实并不如之前：

真的是优化大半天，效率还降低了，😆我想原因就在于 KMP 算法确实比分析 2 中的题解更复杂一些。

总结

本题可以是一道简单题，直接一行return haystack.indexOf(needle); 就能解决。

不过，这样只能说“偷奸耍滑”，站在了巨人的肩膀上，这也正是 Java 的优势，帮我们实现了很多可以直接调用的 API。有时候，如果我们在笔试的时候没有其他思路，先把答案搞出来，然后再去想其他的方法，也是一种策略。

那为了展示我们的实力，我们借助 String 的 substring() 和 equals() 方法，以及一个 for 循环，也能轻松解决这道题。

最后我们还讲了一下 KMP 算法，它的核心思想是利用已经匹配过的信息，对匹配失败的地方进行处理，不断调整匹配串的位置。

总结一下本题我们学到的知识点：

如果觉得视频依然不能满足你的求知欲，那我再补充一些图文教程来辅助你学习：

在我看来，KMP 算法的核心就是求出前缀和后缀的最长公共元素，以"ABCDABD"为例：

一旦求出最长公共元素，问题就变得简单了，只需要根据这个公式 移动位数 = 已匹配的字符数 - 对应的部分匹配值 来移动匹配串的位置即可。

下面是另外一种 KMP 算法的题解，供大家参考：

class Solution {

private void computeNextArray(String needle, int[] next) {        int length = 0; // length用于追踪当前的最长匹配前缀长度        int i = 1;        next[0] = 0; // next数组的第一个元素总是0                while (i < needle.length()) {            if (needle.charAt(i) == needle.charAt(length)) {                // 如果当前字符匹配，增加length，并设置next[i]为length，然后移动到下一个字符                length++;                next[i] = length;                i++;            } else { // 当前字符不匹配                if (length != 0) {                    // 如果length不为0，尝试较短的匹配前缀                    length = next[length - 1];                } else {                    // 如果length为0，说明没有匹配的前缀，设置next[i]为0，并移动到下一个字符                    next[i] = length; // 这里length已经是0了                    i++;                }            }        }    }        public int strStr(String haystack, String needle) {        if (needle.isEmpty()) return 0; // 特殊情况处理：空字符串                int[] next = new int[needle.length()];        // 计算needle的next数组        computeNextArray(needle, next);                int j = 0; // j用于追踪needle中的当前位置        // 遍历haystack字符串        for (int i = 0; i < haystack.length(); i++) {            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {                // 如果字符不匹配，回溯到next[j-1]                j = next[j - 1];            }            if (haystack.charAt(i) == needle.charAt(j)) {                // 如果当前字符匹配，移动到needle中的下一个字符                j++;            }            if (j == needle.length()) {                // 找到匹配，返回起始索引                return i - j + 1;            }        }                // 未找到匹配，返回-1        return -1;    }}

力扣链接：https://leetcode.cn/problems/implement-strstr/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4400+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

鲁迅说过，春节过后，依然要加强学习，不断提高自己。每天一道二哥的 LeetCode 刷题笔记，精神百倍。先用 String 的 indexOf() 方法实现方式来 strStr() 方法，然后再用 KMP 算法来实现一遍，酸爽极了。

开工好多事情要做，忙不过来了，简历要修改，LeetCode 要刷，MySQL 教程要搞，新的项目要启动，但忙碌的感觉还真的挺好，至少让我感觉是积极的。技术派阅读地址：https://paicoding.com/column/7/28

  • 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

  • 这道题可以说完全重写了，给出 3 道大家完全都能掌握的题解（String 的 indexOf、substring+equals+for 循环、KMP 算法）。

  • 增加代码注释，这样大家更容易看懂并掌握题解；

  • 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

  • 增加手绘图，这样大家更容易理解解题思路；

  • 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

  • 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

  • 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

  • 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

难度

简单

示例

例 1

输入：haystack = "sadbutsad", needle = "sad"

解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。

例 2

输入：haystack = "leetcode", needle = "leeto"

解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

分析 1

对于这道题，我们很容易想到 **Java 字符串 **的indexOf()方法，我在二哥的 Java 进阶之路上也帮大家讲过这个方法的实现。

那题解立马就有了，嘿嘿 😜。

class Solution {

    int index = haystack.indexOf(needle);        return index;    }}

并且题解效率非常高：

直接就击败 100% 的 Java 用户。

分析 2

不过 LeetCode 出这道题，显然不是为了让我们直接调用indexOf()方法，而是让我们去实现一个indexOf()方法。

既然如此，我们不妨再来看一下 indexOf 方法的源码（最终 indexOf(String str) 调用的方法）：

JDK8 版本的方法签名是：

static int indexOf(char[] source, int sourceOffset, int sourceCount,

        int fromIndex)

先来看参数：

  • source：主字符串的字符数组。
  • sourceOffset：主字符串的起始偏移量。
  • sourceCount：主字符串中字符的总数。
  • target：要查找的子字符串的字符数组。
  • targetOffset：子字符串的起始偏移量。
  • targetCount：子字符串中字符的总数。
  • fromIndex：开始搜索的索引位置。

再来看逻辑流程：

  • 首先，检查fromIndex是否大于或等于sourceCount。如果是，且targetCount为 0，则返回sourceCount；否则返回-1。
  • 如果fromIndex小于 0，它被设置为 0。
  • 如果targetCount为 0，则直接返回fromIndex，因为空字符串被认为存在于任何位置。
  • 然后，计算最大搜索索引max，这是为了确保搜索时target能够完全位于source中。
  • 接下来，遍历source数组，从sourceOffset + fromIndex开始，直到max，查找与target数组中第一个字符匹配的字符。
  • 一旦找到第一个匹配的字符，就在source中从这个位置开始，尝试匹配整个target数组。
  • 如果所有后续字符都匹配，就返回当前的索引（调整过的，即i - sourceOffset），因为这表示找到了完整的子字符串。
  • 如果遍历完成后未找到匹配的子字符串，则返回-1。

这种实现方式在处理大字符串时效率不如KMP（Knuth-Morris-Pratt）算法，但 JDK 选择了这种更易于理解和实现的方法，足以处理大多数常见的情况。

所以，我们可以按照这个思路来实现我们的strStr()方法。

class Solution {

    // 获取主字符串和子字符串的长度        int sourceCount = haystack.length();        int targetCount = needle.length();                // 如果子字符串为空，则根据题目要求返回0        if (targetCount == 0) {            return 0;        }                // 获取子字符串的第一个字符，用于后续匹配的起点        char first = needle.charAt(0);        // 计算搜索的最大起始位置，确保子字符串能够完全位于主字符串中        int max = sourceCount - targetCount;                // 遍历主字符串        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 + targetCount - 1; // 计算子字符串在主字符串中的结束位置                for (int k = 1; j < end && haystack.charAt(j) == needle.charAt(k); j++, k++);                // 如果整个子字符串都匹配了，返回其在主字符串中的起始索引                if (j == end) {                    return i;                }            }        }        // 如果遍历完成后没有找到匹配的子字符串，返回-1        return -1;    }}

如果觉得上面的代码有点复杂，我们可以稍微简化一下：

class Solution {

    // 如果 needle 是空字符串，则按照题目要求返回 0        if (needle.isEmpty()) {            return 0;        }        // 获取两个字符串的长度        int n = haystack.length();        int m = needle.length();        // 遍历 haystack 字符串        for (int i = 0; i <= n - m; i++) {            // 从 haystack 的第 i 个字符开始，取一个长度为 m 的子字符串            String subStr = haystack.substring(i, i + m);            // 比较这个子字符串与 needle 是否相等            if (subStr.equals(needle)) {                return i; // 如果相等，则返回当前的起始位置            }        }        return -1; // 如果遍历结束都没有找到匹配的位置，则返回 -1    }}

这个方法就非常好懂了，对吧，我们只需要遍历主字符串，然后取出一个长度为子字符串的子串，然后比较两个子串是否相等，如果相等，就返回当前的起始位置。

利用了字符串的 substring() 方法和 equals() 方法，来看一下题解效率：

也非常的高，同样击败了 100% 的 Java 用户。针对这道题，掌握这种方法将就足够了。

分析 3

这里顺带讲一下 KMP 算法，可能有些**球友 **需要。

先让我们从最朴素的暴力算法开始！

假如 haystack = "hello", needle = "ll"，匹配步骤如下图所示：

这样子就能实现较为简单的字符串匹配了，时间复杂度为 ，n 代表原串的长度，m 代表匹配串的长度。

其实分析 2 中的题解就是用的这种思路。

但这样会存在一个问题，当字符串长度非常非常长的时候……这个思路的时间复杂度就不太理想了。

再来看下面这个例子，假如 haystack = "abbacabbab", needle = "abbab"，匹配步骤如下图所示：

这种方式能匹配，但是，不够好！

因为每次匹配失败，匹配串的下标都要回到开头（也就是重新从 needle[0]开始），并且原串的下标也要往回移动（从 haystack[i+1]开始），真的需要这么麻烦吗？

其实真不用，因为匹配串的开头有个ab（字符 b 的前缀），和结尾的ab（字符 b 的后缀）是一样的。

如果匹配串abbab在最后一个位置和原串匹配失败了，那么原串前面肯定存在abba，因为匹配串是以abba开头的，这时候我们要移动的话，就可以保持原串的下标不变（也就是下图中箭头指向的“c”的位置 haystack[4]）然后让匹配串直接从第一个a的位置开始往后匹配，移动匹配串的下标见下图：

这样子是不是就省去了一部分比较的步骤呢？为什么可以这样做呢？

这就不得不说一说 KMP 算法了。

KMP算法是由 Knuth、Pratt 和 Morris 在 1977 年共同发布的，用来解决字符串匹配问题的算法。

KMP 算法核心思想概括成一句话就是 利用已经匹配过的残余信息，使原串的比较位置保持不变，而匹配串的比较位置尽快移动到有效的地方。

回顾之前的暴力步骤，如果从 haystack[i] 开始的那一趟比较失败了，算法会尝试从 haystack[i+1] 开始比较。这种行为，属于典型的“没有从之前的错误中学到东西”。

我们应当注意到，一次失败的匹配，会给我们提供宝贵的信息——再次观察暴力算法中的移动方法，匹配串abbab在第一次匹配失败后，我们应该如何移动原串和匹配串的下标呢？

答案见下图，原创的位置保持不变，只需要移动匹配串到第二个 b 的位置就可以了。因为以最后一个位置的 b 结尾的后缀，最多能与前缀ab匹配。

也就是图中的蓝色部分与绿色部分相匹配。

所以……在匹配失败之后，我们能够让匹配串的比较位置以最快的速度移动到的位置，就是——以 当前比较位置结尾的能够匹配的最长前缀 ！！

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

到这里，我们应该清楚 KMP 为什么相比于暴力解法更快：

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

前缀和后缀又是怎么求出来的呢？

这就涉及到了 KMP 算法 的next[]数组，它就是匹配串位置能移动到的有效的且最远的位置。

next[]数组到底要怎么求呢？我们显然不能挨个去对每个前缀后缀处理，因为这样子时间开销太大了！

其实只需要匹配串对自身 匹配 一次就可以得出了。

class GetNext{

public void getNext(String p, int[] next) {        // next数组的第一个元素总是-1，这是KMP算法的约定，表示不存在更短的相同前缀和后缀        next[0] = -1;                // posK表示前缀的最后一个字符位置，posJ表示后缀的最后一个字符位置        int posK = -1, posJ = 0;                // 遍历模式字符串p来计算每个位置的next值        while (posJ < p.length() - 1) { // 注意这里posJ < p.length() - 1，因为next数组的最后一个值是不需要计算的            // 当posK为-1时，表示我们需要从头开始匹配或者p.charAt(posK) == p.charAt(posJ)，即当前字符匹配成功            if (posK == -1 || p.charAt(posK) == p.charAt(posJ)) {                posJ++;                posK++;                // 设置next数组的值。此时，posK也表示posJ位置字符之前的p子串中，前缀和后缀最长公共元素的长度                next[posJ] = posK;            } else {                // 如果匹配失败，则根据next数组回溯。即，让posK回到上一个可能匹配的位置                posK = next[posK];            }        }    }}

上述代码中，我们用posJ和posK来求解next[]数组，我们来模拟一遍。

posK就相当于对匹配串自己 匹配 的一个变量，只不过它是后缀来匹配前缀，这样子我们就求解出了next[]数组，然后只需要按照next[]数组的值，在匹配串与原串失配的时候，把匹配串的位置相应的移动即可。

这次，我们再来用next[]数组来优化我们的字符串匹配过程和之前朴素想法一对比……：

是不是节省了很大一部分，而在数据规模越大的情况下，我们能够优化的也就越多！

class Solution {

private void getNext(String p, int[] next) {        next[0] = -1; // 初始化next数组的第一个值为-1        int posK = -1, posJ = 0; // posK和posJ分别表示前缀和后缀的比较位置                // 遍历模式字符串p来计算next数组的值        while (posJ < p.length() - 1) {            // 如果posK为-1，或当前字符匹配成功，则向前移动posK和posJ            if (posK == -1 || p.charAt(posK) == p.charAt(posJ)) {                posJ++;                posK++;                next[posJ] = posK; // 更新next数组            } else {                // 如果当前字符匹配失败，根据next数组回溯posK                posK = next[posK];            }        }    }        // strStr方法实现了KMP算法来找出needle在haystack中的第一次出现的位置    public int strStr(String haystack, String needle) {        if (needle.isEmpty()) return 0; // 特殊情况处理：空字符串                int[] next = new int[needle.length() + 1]; // 初始化next数组        getNext(needle, next); // 调用getNext方法填充next数组                int posI = 0, posJ = 0; // posI和posJ分别表示在haystack和needle中的当前位置                // 在haystack中遍历，尝试匹配needle        while (posI < haystack.length() && posJ < needle.length()) {            // 如果posJ为-1（即需要从头开始匹配）或当前字符匹配成功            if (posJ == -1 || haystack.charAt(posI) == needle.charAt(posJ)) {                posI++;                posJ++;            } else {                // 如果当前字符匹配失败，根据next数组回溯posJ                posJ = next[posJ];            }        }                // 如果完全匹配，返回匹配的起始位置        if (posJ == needle.length()) return posI - posJ;        // 如果匹配失败，返回-1        return -1;    }}

时间复杂度：

我们利用 已经匹配过的信息 来对匹配失败的地方进行处理，不断调整匹配串的位置，时间复杂度就得到了优化。

但 LeetCode 测出来的效果其实并不如之前：

真的是优化大半天，效率还降低了，😆我想原因就在于 KMP 算法确实比分析 2 中的题解更复杂一些。

总结

本题可以是一道简单题，直接一行return haystack.indexOf(needle); 就能解决。

不过，这样只能说“偷奸耍滑”，站在了巨人的肩膀上，这也正是 Java 的优势，帮我们实现了很多可以直接调用的 API。有时候，如果我们在笔试的时候没有其他思路，先把答案搞出来，然后再去想其他的方法，也是一种策略。

那为了展示我们的实力，我们借助 String 的 substring() 和 equals() 方法，以及一个 for 循环，也能轻松解决这道题。

最后我们还讲了一下 KMP 算法，它的核心思想是利用已经匹配过的信息，对匹配失败的地方进行处理，不断调整匹配串的位置。

总结一下本题我们学到的知识点：

如果觉得视频依然不能满足你的求知欲，那我再补充一些图文教程来辅助你学习：

在我看来，KMP 算法的核心就是求出前缀和后缀的最长公共元素，以"ABCDABD"为例：

一旦求出最长公共元素，问题就变得简单了，只需要根据这个公式 移动位数 = 已匹配的字符数 - 对应的部分匹配值 来移动匹配串的位置即可。

下面是另外一种 KMP 算法的题解，供大家参考：

class Solution {

private void computeNextArray(String needle, int[] next) {        int length = 0; // length用于追踪当前的最长匹配前缀长度        int i = 1;        next[0] = 0; // next数组的第一个元素总是0                while (i < needle.length()) {            if (needle.charAt(i) == needle.charAt(length)) {                // 如果当前字符匹配，增加length，并设置next[i]为length，然后移动到下一个字符                length++;                next[i] = length;                i++;            } else { // 当前字符不匹配                if (length != 0) {                    // 如果length不为0，尝试较短的匹配前缀                    length = next[length - 1];                } else {                    // 如果length为0，说明没有匹配的前缀，设置next[i]为0，并移动到下一个字符                    next[i] = length; // 这里length已经是0了                    i++;                }            }        }    }        public int strStr(String haystack, String needle) {        if (needle.isEmpty()) return 0; // 特殊情况处理：空字符串                int[] next = new int[needle.length()];        // 计算needle的next数组        computeNextArray(needle, next);                int j = 0; // j用于追踪needle中的当前位置        // 遍历haystack字符串        for (int i = 0; i < haystack.length(); i++) {            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {                // 如果字符不匹配，回溯到next[j-1]                j = next[j - 1];            }            if (haystack.charAt(i) == needle.charAt(j)) {                // 如果当前字符匹配，移动到needle中的下一个字符                j++;            }            if (j == needle.length()) {                // 找到匹配，返回起始索引                return i - j + 1;            }        }                // 未找到匹配，返回-1        return -1;    }}

力扣链接：https://leetcode.cn/problems/implement-strstr/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4400+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

鲁迅说过，春节过后，依然要加强学习，不断提高自己。每天一道二哥的 LeetCode 刷题笔记，精神百倍。先用 String 的 indexOf() 方法实现方式来 strStr() 方法，然后再用 KMP 算法来实现一遍，酸爽极了。

开工好多事情要做，忙不过来了，简历要修改，LeetCode 要刷，MySQL 教程要搞，新的项目要启动，但忙碌的感觉还真的挺好，至少让我感觉是积极的。技术派阅读地址：https://paicoding.com/column/7/28

  • 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

  • 这道题可以说完全重写了，给出 3 道大家完全都能掌握的题解（String 的 indexOf、substring+equals+for 循环、KMP 算法）。

  • 增加代码注释，这样大家更容易看懂并掌握题解；

  • 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

  • 增加手绘图，这样大家更容易理解解题思路；

  • 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

  • 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

  • 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

  • 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

难度

简单

示例

例 1

输入：haystack = "sadbutsad", needle = "sad"

解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。

例 2

输入：haystack = "leetcode", needle = "leeto"

解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

分析 1

对于这道题，我们很容易想到 **Java 字符串 **的indexOf()方法，我在二哥的 Java 进阶之路上也帮大家讲过这个方法的实现。

那题解立马就有了，嘿嘿 😜。

class Solution {

    int index = haystack.indexOf(needle);        return index;    }}

并且题解效率非常高：

直接就击败 100% 的 Java 用户。

分析 2

不过 LeetCode 出这道题，显然不是为了让我们直接调用indexOf()方法，而是让我们去实现一个indexOf()方法。

既然如此，我们不妨再来看一下 indexOf 方法的源码（最终 indexOf(String str) 调用的方法）：

JDK8 版本的方法签名是：

static int indexOf(char[] source, int sourceOffset, int sourceCount,

        int fromIndex)

先来看参数：

  • source：主字符串的字符数组。
  • sourceOffset：主字符串的起始偏移量。
  • sourceCount：主字符串中字符的总数。
  • target：要查找的子字符串的字符数组。
  • targetOffset：子字符串的起始偏移量。
  • targetCount：子字符串中字符的总数。
  • fromIndex：开始搜索的索引位置。

再来看逻辑流程：

  • 首先，检查fromIndex是否大于或等于sourceCount。如果是，且targetCount为 0，则返回sourceCount；否则返回-1。
  • 如果fromIndex小于 0，它被设置为 0。
  • 如果targetCount为 0，则直接返回fromIndex，因为空字符串被认为存在于任何位置。
  • 然后，计算最大搜索索引max，这是为了确保搜索时target能够完全位于source中。
  • 接下来，遍历source数组，从sourceOffset + fromIndex开始，直到max，查找与target数组中第一个字符匹配的字符。
  • 一旦找到第一个匹配的字符，就在source中从这个位置开始，尝试匹配整个target数组。
  • 如果所有后续字符都匹配，就返回当前的索引（调整过的，即i - sourceOffset），因为这表示找到了完整的子字符串。
  • 如果遍历完成后未找到匹配的子字符串，则返回-1。

这种实现方式在处理大字符串时效率不如KMP（Knuth-Morris-Pratt）算法，但 JDK 选择了这种更易于理解和实现的方法，足以处理大多数常见的情况。

所以，我们可以按照这个思路来实现我们的strStr()方法。

class Solution {

    // 获取主字符串和子字符串的长度        int sourceCount = haystack.length();        int targetCount = needle.length();                // 如果子字符串为空，则根据题目要求返回0        if (targetCount == 0) {            return 0;        }                // 获取子字符串的第一个字符，用于后续匹配的起点        char first = needle.charAt(0);        // 计算搜索的最大起始位置，确保子字符串能够完全位于主字符串中        int max = sourceCount - targetCount;                // 遍历主字符串        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 + targetCount - 1; // 计算子字符串在主字符串中的结束位置                for (int k = 1; j < end && haystack.charAt(j) == needle.charAt(k); j++, k++);                // 如果整个子字符串都匹配了，返回其在主字符串中的起始索引                if (j == end) {                    return i;                }            }        }        // 如果遍历完成后没有找到匹配的子字符串，返回-1        return -1;    }}

如果觉得上面的代码有点复杂，我们可以稍微简化一下：

class Solution {

    // 如果 needle 是空字符串，则按照题目要求返回 0        if (needle.isEmpty()) {            return 0;        }        // 获取两个字符串的长度        int n = haystack.length();        int m = needle.length();        // 遍历 haystack 字符串        for (int i = 0; i <= n - m; i++) {            // 从 haystack 的第 i 个字符开始，取一个长度为 m 的子字符串            String subStr = haystack.substring(i, i + m);            // 比较这个子字符串与 needle 是否相等            if (subStr.equals(needle)) {                return i; // 如果相等，则返回当前的起始位置            }        }        return -1; // 如果遍历结束都没有找到匹配的位置，则返回 -1    }}

这个方法就非常好懂了，对吧，我们只需要遍历主字符串，然后取出一个长度为子字符串的子串，然后比较两个子串是否相等，如果相等，就返回当前的起始位置。

利用了字符串的 substring() 方法和 equals() 方法，来看一下题解效率：

也非常的高，同样击败了 100% 的 Java 用户。针对这道题，掌握这种方法将就足够了。

分析 3

这里顺带讲一下 KMP 算法，可能有些**球友 **需要。

先让我们从最朴素的暴力算法开始！

假如 haystack = "hello", needle = "ll"，匹配步骤如下图所示：

这样子就能实现较为简单的字符串匹配了，时间复杂度为 ，n 代表原串的长度，m 代表匹配串的长度。

其实分析 2 中的题解就是用的这种思路。

但这样会存在一个问题，当字符串长度非常非常长的时候……这个思路的时间复杂度就不太理想了。

再来看下面这个例子，假如 haystack = "abbacabbab", needle = "abbab"，匹配步骤如下图所示：

这种方式能匹配，但是，不够好！

因为每次匹配失败，匹配串的下标都要回到开头（也就是重新从 needle[0]开始），并且原串的下标也要往回移动（从 haystack[i+1]开始），真的需要这么麻烦吗？

其实真不用，因为匹配串的开头有个ab（字符 b 的前缀），和结尾的ab（字符 b 的后缀）是一样的。

如果匹配串abbab在最后一个位置和原串匹配失败了，那么原串前面肯定存在abba，因为匹配串是以abba开头的，这时候我们要移动的话，就可以保持原串的下标不变（也就是下图中箭头指向的“c”的位置 haystack[4]）然后让匹配串直接从第一个a的位置开始往后匹配，移动匹配串的下标见下图：

这样子是不是就省去了一部分比较的步骤呢？为什么可以这样做呢？

这就不得不说一说 KMP 算法了。

KMP算法是由 Knuth、Pratt 和 Morris 在 1977 年共同发布的，用来解决字符串匹配问题的算法。

KMP 算法核心思想概括成一句话就是 利用已经匹配过的残余信息，使原串的比较位置保持不变，而匹配串的比较位置尽快移动到有效的地方。

回顾之前的暴力步骤，如果从 haystack[i] 开始的那一趟比较失败了，算法会尝试从 haystack[i+1] 开始比较。这种行为，属于典型的“没有从之前的错误中学到东西”。

我们应当注意到，一次失败的匹配，会给我们提供宝贵的信息——再次观察暴力算法中的移动方法，匹配串abbab在第一次匹配失败后，我们应该如何移动原串和匹配串的下标呢？

答案见下图，原创的位置保持不变，只需要移动匹配串到第二个 b 的位置就可以了。因为以最后一个位置的 b 结尾的后缀，最多能与前缀ab匹配。

也就是图中的蓝色部分与绿色部分相匹配。

所以……在匹配失败之后，我们能够让匹配串的比较位置以最快的速度移动到的位置，就是——以 当前比较位置结尾的能够匹配的最长前缀 ！！

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

到这里，我们应该清楚 KMP 为什么相比于暴力解法更快：

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

前缀和后缀又是怎么求出来的呢？

这就涉及到了 KMP 算法 的next[]数组，它就是匹配串位置能移动到的有效的且最远的位置。

next[]数组到底要怎么求呢？我们显然不能挨个去对每个前缀后缀处理，因为这样子时间开销太大了！

其实只需要匹配串对自身 匹配 一次就可以得出了。

class GetNext{

public void getNext(String p, int[] next) {        // next数组的第一个元素总是-1，这是KMP算法的约定，表示不存在更短的相同前缀和后缀        next[0] = -1;                // posK表示前缀的最后一个字符位置，posJ表示后缀的最后一个字符位置        int posK = -1, posJ = 0;                // 遍历模式字符串p来计算每个位置的next值        while (posJ < p.length() - 1) { // 注意这里posJ < p.length() - 1，因为next数组的最后一个值是不需要计算的            // 当posK为-1时，表示我们需要从头开始匹配或者p.charAt(posK) == p.charAt(posJ)，即当前字符匹配成功            if (posK == -1 || p.charAt(posK) == p.charAt(posJ)) {                posJ++;                posK++;                // 设置next数组的值。此时，posK也表示posJ位置字符之前的p子串中，前缀和后缀最长公共元素的长度                next[posJ] = posK;            } else {                // 如果匹配失败，则根据next数组回溯。即，让posK回到上一个可能匹配的位置                posK = next[posK];            }        }    }}

上述代码中，我们用posJ和posK来求解next[]数组，我们来模拟一遍。

posK就相当于对匹配串自己 匹配 的一个变量，只不过它是后缀来匹配前缀，这样子我们就求解出了next[]数组，然后只需要按照next[]数组的值，在匹配串与原串失配的时候，把匹配串的位置相应的移动即可。

这次，我们再来用next[]数组来优化我们的字符串匹配过程和之前朴素想法一对比……：

是不是节省了很大一部分，而在数据规模越大的情况下，我们能够优化的也就越多！

class Solution {

private void getNext(String p, int[] next) {        next[0] = -1; // 初始化next数组的第一个值为-1        int posK = -1, posJ = 0; // posK和posJ分别表示前缀和后缀的比较位置                // 遍历模式字符串p来计算next数组的值        while (posJ < p.length() - 1) {            // 如果posK为-1，或当前字符匹配成功，则向前移动posK和posJ            if (posK == -1 || p.charAt(posK) == p.charAt(posJ)) {                posJ++;                posK++;                next[posJ] = posK; // 更新next数组            } else {                // 如果当前字符匹配失败，根据next数组回溯posK                posK = next[posK];            }        }    }        // strStr方法实现了KMP算法来找出needle在haystack中的第一次出现的位置    public int strStr(String haystack, String needle) {        if (needle.isEmpty()) return 0; // 特殊情况处理：空字符串                int[] next = new int[needle.length() + 1]; // 初始化next数组        getNext(needle, next); // 调用getNext方法填充next数组                int posI = 0, posJ = 0; // posI和posJ分别表示在haystack和needle中的当前位置                // 在haystack中遍历，尝试匹配needle        while (posI < haystack.length() && posJ < needle.length()) {            // 如果posJ为-1（即需要从头开始匹配）或当前字符匹配成功            if (posJ == -1 || haystack.charAt(posI) == needle.charAt(posJ)) {                posI++;                posJ++;            } else {                // 如果当前字符匹配失败，根据next数组回溯posJ                posJ = next[posJ];            }        }                // 如果完全匹配，返回匹配的起始位置        if (posJ == needle.length()) return posI - posJ;        // 如果匹配失败，返回-1        return -1;    }}

时间复杂度：

我们利用 已经匹配过的信息 来对匹配失败的地方进行处理，不断调整匹配串的位置，时间复杂度就得到了优化。

但 LeetCode 测出来的效果其实并不如之前：

真的是优化大半天，效率还降低了，😆我想原因就在于 KMP 算法确实比分析 2 中的题解更复杂一些。

总结

本题可以是一道简单题，直接一行return haystack.indexOf(needle); 就能解决。

不过，这样只能说“偷奸耍滑”，站在了巨人的肩膀上，这也正是 Java 的优势，帮我们实现了很多可以直接调用的 API。有时候，如果我们在笔试的时候没有其他思路，先把答案搞出来，然后再去想其他的方法，也是一种策略。

那为了展示我们的实力，我们借助 String 的 substring() 和 equals() 方法，以及一个 for 循环，也能轻松解决这道题。

最后我们还讲了一下 KMP 算法，它的核心思想是利用已经匹配过的信息，对匹配失败的地方进行处理，不断调整匹配串的位置。

总结一下本题我们学到的知识点：

如果觉得视频依然不能满足你的求知欲，那我再补充一些图文教程来辅助你学习：

在我看来，KMP 算法的核心就是求出前缀和后缀的最长公共元素，以"ABCDABD"为例：

一旦求出最长公共元素，问题就变得简单了，只需要根据这个公式 移动位数 = 已匹配的字符数 - 对应的部分匹配值 来移动匹配串的位置即可。

下面是另外一种 KMP 算法的题解，供大家参考：

class Solution {

private void computeNextArray(String needle, int[] next) {        int length = 0; // length用于追踪当前的最长匹配前缀长度        int i = 1;        next[0] = 0; // next数组的第一个元素总是0                while (i < needle.length()) {            if (needle.charAt(i) == needle.charAt(length)) {                // 如果当前字符匹配，增加length，并设置next[i]为length，然后移动到下一个字符                length++;                next[i] = length;                i++;            } else { // 当前字符不匹配                if (length != 0) {                    // 如果length不为0，尝试较短的匹配前缀                    length = next[length - 1];                } else {                    // 如果length为0，说明没有匹配的前缀，设置next[i]为0，并移动到下一个字符                    next[i] = length; // 这里length已经是0了                    i++;                }            }        }    }        public int strStr(String haystack, String needle) {        if (needle.isEmpty()) return 0; // 特殊情况处理：空字符串                int[] next = new int[needle.length()];        // 计算needle的next数组        computeNextArray(needle, next);                int j = 0; // j用于追踪needle中的当前位置        // 遍历haystack字符串        for (int i = 0; i < haystack.length(); i++) {            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {                // 如果字符不匹配，回溯到next[j-1]                j = next[j - 1];            }            if (haystack.charAt(i) == needle.charAt(j)) {                // 如果当前字符匹配，移动到needle中的下一个字符                j++;            }            if (j == needle.length()) {                // 找到匹配，返回起始索引                return i - j + 1;            }        }                // 未找到匹配，返回-1        return -1;    }}

力扣链接：https://leetcode.cn/problems/implement-strstr/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4400+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412
028.实现 strStr()
https://clxhxhhr.top/posts/2453/
作者
clxstart
发布于
2026-09-19
许可协议
CC BY-NC-SA 4.0
027.移除元素
029.两数相除
评论
0 条
还没有评论，先写一条吧。
☰ 文章目录