Untitled

class Solution {
public:
    vector<int> preprocess(string s){
        int n = s.size(), prefix_len = 0, i = 1;
        vector<int>next = {0};
        while(i < n){
            if(s[prefix_len] == s[i]){//Find common between prefix and suffix
                prefix_len++;
                next.push_back(prefix_len);
                i++;
            }
            else{
                if(prefix_len > 0)//Go backward 
                    prefix_len = next[prefix_len-1];
                else{
                    next.push_back(0);
                    i++;
                }
            }
        }
        return next;
    }
    int strStr(string source, string target) {
        int m = source.size(), n = target.size();
        if(source == target)
            return 0;
        vector<int>next = preprocess(target);
        int i = 0, j = 0;//i: source, j: target
        while(i < m){
            if(source[i] == target[j]){//Match
                i++;
                j++;
            }
            else if(j > 0)//Go backward to find common prefix and suffix
                j = next[j-1];
            else//Does not match at first char
                i++;
            if(j == n)
                return i-j;
        }
        return -1;
    }
    //KMP Algorithm
    //Time O(m+n)
    //Space O(n)
};