LEETCODE ALGORITHM:28. Implement strStr()

发表于 更新于 分类于 Waline： 阅读次数：

题目

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

题解

用c的strstr，c++的find都是双百，但是这题的意义就没了

kmp的next数组实际上是最大前缀长度+1，加1是因为当比较到i位的时候已经不相等的，只能按照前面i-1位的最长公共前缀进行移动

计算next数组类似于对自身运用kmp算法

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
class Solution {
private:
    void get_next(string t,vector<int> &next)
    {
        int i=0,j=-1;
        next[0]=-1;
        while(i<t.length())
        {
            while(j>=0&&t[i]!=t[j]) j=next[j];
            //注意这里是while，只要不相等就前移j，直到j到达首位，增加i
            ++i;++j;
            next[i]=j;
        }
    }
public:
    int strStr(string haystack, string needle) {
        //return haystack.find(needle);
        if(needle.length()==0) return 0;
        int hs=haystack.size(),ns=needle.size();
        vector<int> next(needle.size()+1);
        get_next(needle,next);
        int i=0,j=0;
        while(i<hs&&j<ns)
        {//j==-1表示当前hay的i字符和needle的一个字节也不相等，要后移i
            if(j==-1||haystack[i]==needle[j])
            {
                ++i;++j;
            }else{
                j=next[j];
            }
        }
        //return next[3];
        if(j>=ns) return i-ns;//i为匹配结束时的下标，要减去needle字符串的长度
        else return -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
//区别在计算next数组，不用while当数量大时更高效
class Solution {
private:
    void get_next(string t,vector<int> &next)
    {
        int i=0,j=-1;
        next[0]=-1;
        while(i<t.length())
        {
            if(j==-1||t[i]==t[j])
            {
                ++i;++j;next[i]=j;
            }else{
                j=next[j];
            }
        }
    }
public:
    int strStr(string haystack, string needle) {
        if(needle.length()==0) return 0;
        int hs=haystack.size(),ns=needle.size();
        vector<int> next(needle.size()+1);
        get_next(needle,next);
        int i=0,j=0;
        while(i<hs&&j<ns)
        {
            if(j==-1||haystack[i]==needle[j])
            {
                ++i;++j;
            }else{
                j=next[j];
            }
        }
        //return next[3];
        if(j>=ns) return i-ns;
        else return -1;
    }
};