class Solution {
public:
    int strStr(string haystack, string needle) {
        int lenH = haystack.size(), lenN = needle.size();
        if(lenH < lenN)return -1;

        //KMP, calculate next array
        vector<int> next(lenN + 1, -1);
        int k = -1, i = 0;
        while(i < lenN)
        {
            if(k == -1 || needle[i] == needle[k])
                next[++i] = ++k;
            else
                k = next[k];
        }

        int j = 0;
        i = 0;
        while(i < lenH && j < lenN)
        {
            if(j == -1 || haystack[i] == needle[j])
            {
                ++i;
                ++j;
            }
            else
                j = next[j];
        }

        return j == lenN? i - lenN: -1;
    }
};