LeetCode——28. Implement strStr()

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()){
            return 0;
        }
        
        vector<int> next;
        int i = 0;
        int j = 0;
        int sLen = haystack.size();
        int tLen = needle.size();
  
        next = getNext(needle);
  
        while((i<sLen)&&(j<tLen)){
            if((j==-1)||(haystack[i]==needle[j])){
                i++;
                j++;
            }
            else{
                j = next[j];
            }
        }
  
        if(j==tLen){
            return i-j;
        }
  
        return -1;
    }
 
    vector<int> getNext(string pattern){
        vector<int> next;
        int j = -1;
        int i = 0;
        int len = pattern.size();
     
        next.push_back(-1);
     
        while(i<len-1){
            if(j==-1||pattern[i] == pattern[j]){
                i++;
                j++;
                next.push_back(j);
            }
            else{
                j = next[j];
            }
        }
        return next;
    }
};

    vector<int> getNext(string pattern){
        vector<int> next;
        int j = -1;
        int i = 0;
        int len = pattern.size();
     
        next.push_back(-1);
     
        while(i<len-1){
            if(j==-1||pattern[i] == pattern[j]){
                i++;
                j++;
                if(pattern[j]!=pattern[i]){
                    next.push_back(j);                
                }
                else{
                    next.push_back(next[j]);
                }
            }
            else{
                j = next[j];
            }
        }
        return next;
    }