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

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

class Solution {
public:
    void getNext(int* next,const string &s){
        int j=-1;
        next[0]=j;
        for(int i=1;i<s.size();i++){
            while(j>=0&&s[i]!=s[j+1]){
                j=next[j];//回退
            }
            if(s[i]==s[j+1]){
                j++;
            }
                next[i]=j;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0){  //当needle的size为0
            return 0;
        }
        int next[needle.size()];//初始化数组
        getNext(next,needle);//get next数组
        int j=-1;
        for(int i=0;i<haystack.size();i++){
            while(j>=0&&haystack[i]!=needle[j+1]){
                j=next[j];//回退
            }
            if(haystack[i]==needle[j+1]){
                j++;
            }
            if(j==(needle.size()-1)){
                return (i-needle.size()+1);
            }
        }
        return -1;
    }
};