leetcode题解：28.找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标

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

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

思路

我们可以让字符串 needle\textit{needle}needle 与字符串 haystack\textit{haystack}haystack 的所有长度为 mmm 的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1

复杂度分析

时间复杂度：O(n×m)O(n \times m)O(n×m)，其中 nnn 是字符串 haystack\textit{haystack}haystack 的长度，mmm 是字符串 needle\textit{needle}needle 的长度。最坏情况下我们需要将字符串 needle\textit{needle}needle 与字符串 haystack\textit{haystack}haystack 的所有长度为 mmm 的子串均匹配一次。

空间复杂度：O(1)O(1)O(1)。我们只需要常数的空间保存若干变量。

题解

class Solution {
public:
    int strStr(string haystack, string needle) {
      
        return haystack.find(needle);
    }
};

推荐学习 https://xxetb.xetslk.com/s/p5Ibb