28. Implement strStr()

KMP算法

problem description

Implement strStr().

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

Example 1:

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

Example 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().

algorithm thought

这题其实暴力发就能解决，就是单纯的字符串匹配。但是太慢了，历史上也有几位大佬觉得这种方法很慢。并且确实有可以优化的地方，如果是一个人来匹配字符串，当一个成功了很多次之后最后一个字符匹配失败了，他不会前进一位重新来。而是跳过已知的不匹配的情况。

我描述肯定不是很好懂，可以看看这个网站的例子:https://subetter.com/algorithm/kmp-algorithm.html

kmp最关键的是构建next数组，然后就很好匹配了。

code

//最原始的暴力法
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size()==0)
            return 0;
        if(haystack.size()==0){
                return -1;
        }
        for(int i=0;i<haystack.length();++i){
            if(haystack[i]==needle[0]){
                int j=1;
                for(int k=i+1;j<needle.length()&&k<haystack.length();++j,++k){
                    if(haystack[k]!=needle[j])
                        break;
                }
                if(j==needle.length())
                    return i;
            }
        }
        return -1;
    }
};

//kmp算法
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size()==0)
            return 0;
        vector<int>next(needle.size(),-1);    
        getnext(next,needle);
        int i=0;
        int j=0;
        while(i<int(haystack.size())&&j<int(needle.size())){
            //cout<<i<<'-'<<j<<' ';
            if(j==-1||needle[j]==haystack[i]){
                ++i;++j;
            }else
                j=next[j];
            //cout<<j<<needle.size();
        }
        if(j==needle.size()){
            return i-needle.size();
        }
        return -1;
    }
    void getnext(vector<int>&next,string&needle){
        int size=needle.size()-1;
        int i=0;
        int j=-1;
        //next[0]=-1;
        while(i<size){
            if(j==-1||needle[i]==needle[j]){
                i++;j++;
                if(needle[i]!=needle[j])
                    next[i]=j;
                else
                    next[i]=next[j];
            }else
                j=next[j];
        }
    }
};

algorithm analysis

暴力法两个循环，heystack字符串长m，needle字符串长n，时间复杂度是O(nm)

kmp算法，求出next数组时间复杂度是O(n),匹配时间复杂度是O(m)，m>n。最后时间复杂度是O(m)