一、题目描述
给你两个字符串 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 仅由小写英文字符组成
三、解题思路
- 基本思路:
采用KMP算法; - 具体思路:
- 计算 next 数组:可以暴力计算,也可以优化方法;这里介绍优化方法:
- ①
next[0]
和next[1]
必定为 0 ,从next[2]
开始计算。next[i] 表示前 i 个字母相同,第 i+1 个字母不同时,应该跳转的位置。 例如:
以 i=4 为例,表示前 4 个字母相同,但第 5 个字母不同,正常情况下,匹配字符串 ABCABD 匹配到第 5 个字母 B 时遇到不匹配字母时,则要从头即 A 开始重新匹配,但是其实我们已经匹配过前 4 个字母,我们知道前 4 个字母的情况,即待匹配序列为 …ABCA#**** 的形式,我们可以不需要返回从 A 开始,可以直接从 # 位置开始与匹配字符串的第二个字母 B 进行匹配,即 next 可以不用等于 0 ,可以等于 1 。【第一个字母下标 0,第二个字母下标为 1】 - ② 定义变量 p ,表示相同前缀下标,初始化为 0 ;定义变量 i ,用于遍历 next 数组,初始化为 2 ;
- ③ 判断
needle[i-1]
和needle[p]
是否相等,相等表示他们有相同的前缀,则将p+1
的值赋值给next[i]
;否则,表示他们前缀不同,则判断 p 是否等于 0 ,等于 0 表示不存在相同的前缀,则 next = 0 ,不等于 0 表示可能存在相同前缀,令 p = next[p] ,继续寻找相同前缀;
- ①
- 进行匹配:
- ① 定义变量 i 和 j ,用于遍历待匹配字符串和匹配字符串,初始化都为 0 ;
- ② 遍历字符串,如果两个字母相同,则匹配下一个字母,如果匹配字符串都匹配完,则返回下标;如果字母不同,则判断是否为匹配字符串的第一个字母,是则表示第一个字母都不一样,则待匹配字符串下移一个字母,不是则表示可能存在匹配前缀,匹配字符串根据 next 数组移动要对应位置。遍历结束则表示不存在匹配的字符串,则返回 -1 。
- 计算 next 数组:可以暴力计算,也可以优化方法;这里介绍优化方法:
四、参考代码
时间复杂度: O ( n + m ) \Omicron(n+m) O(n+m) 【 m 为待匹配字符串长度,n 为匹配字符串长度】
空间复杂度: O ( n ) \Omicron(n) O(n)
class Solution {
public:void setNext(vector<int> &next,string needle){int n=next.size();int p=0;next[0]=next[1]=0;for(int i=2;i<n;){if(needle[i-1]==needle[p]){next[i++]=++p;}else{if(p==0){next[i++]=0;}else{p=next[p];}}}}int strStr(string haystack, string needle) {int n=needle.size();int m=haystack.size();int j=0;vector<int> next(n+1,0);setNext(next,needle);for(int i=0;i<m;){if(haystack[i]==needle[j]){j++;i++;if(j==n){return i-j;}}else{if(j==0)i++;j=next[j];}}return -1;}
};