28. Implement strStr()

https://leetcode.com/problems/implement-strstr/description/
Solution. KMP search.
    vector<int> calcLPS(const string& pat) {
        vector<int> lps(pat.size(), 0);
        int len = 0;
        lps[0] = 0;
        int i = 1;
        while(i<pat.size()) {
            if(pat[len] == pat[i]) {
                len++;
                lps[i++] = len;
            }
            else {
                if(len != 0)
                    len = lps[len-1];
                else
                    lps[i++] = 0;
            }
        }
        return lps;
    }
    int strStr(string haystack, string needle) {
        if(needle.size() == 0) return 0;
        if(haystack.size() < needle.size()) return -1;
        vector<int> lps = calcLPS(needle);
        int i = 0;
        int j = 0;
        while(i<haystack.size()) {
            if(haystack[i] == needle[j]) {
                i++;
                j++;
            }
            if(j == needle.size()) return i-j;
            else if(i<haystack.size() && haystack[i] != needle[j]) {
                if(j != 0) j = lps[j-1];
                else i++;
            }
        }
        return -1;
    }