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

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

示例 1：

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

示例 2：

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

方法一 暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int strStr(string haystack, string needle) {
        int len_h=haystack.size();
        int len_n=needle.size();
        int i=0;
        while(i<len_h){
            if(haystack[i]!=needle[0]) i++; //匹配不成功继续遍历
            else{ //和needle首元素匹配成功
                int j=0;
                int t=i;
                while(j<len_n){ 
                    if(needle[j]==haystack[i]){
                        i++;
                        j++;
                    }
                    else{ // i回溯到不匹配的位置的下一个位置。
                        i=t+1;
                        break;
                    }

                }
                if(j==len_n) return i-len_n;
            }
        }
        return -1;
    }
};



//稍微优化一下
class Solution {
public:
    int strStr(string h, string n) {
        int len_h=h.size();
        int len_n=n.size();
        for(int i=0;i<len_h;i++){
            int j=0;
            int t=i;
            while(h[t]==n[j]&&j<len_n){
                t++;
                j++;
            }
            if(j==len_n) return t-j;
        }
        return -1;
    }
};

方法二 KMP算法

next数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int strStr(string haystack, string needle) {
        int len_h=haystack.size();
        int len_n=needle.size();
        vector<int>ne(len_n+1,0);
        for(int i=2,j=0;i<=len_n;i++){
            while(j&&needle[i-1]!=needle[j])
                j=ne[j];
            if(needle[i-1]==needle[j])
                j++;
            ne[i]=j;
        }
        for(int i=1,j=0;i<=len_h;i++){
            while(j&&haystack[i-1]!=needle[j])
                j=ne[j];
            if(haystack[i-1]==needle[j])
                j++;
            if(j==len_n) return i-len_n;
        }
        return -1;
    }
};