leetcode 28. 实现 strStr() （KMP算法实现）

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

实现 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

🧡 算法分析

朴素做法：
直接按照一个一个字符进行对比，如果对比结束，长度和需要对比的字符串长度一样，返回下标即可

进阶做法：KMP算法
算法步骤：参考这篇博客

💚 代码实现

class Solution {
public:
    int strStr(string haystack, string needle) {
        // 朴素做法
        int a = haystack.size(), b = needle.size();
        for(int i = 0; i <= a - b; i ++)
        {
            int j = i, k = 0;
            while(k < b && haystack[j] == needle[k]) j ++, k ++;
            if(k == b) return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

执行结果：

💙 时间复杂度分析

朴素做法： 时间复杂度为O(nm)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！