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;
    }

459. Repeated Substring Pattern

https://leetcode.com/problems/repeated-substring-pattern/description/
Solution 0. Use KMP algorithm. 
Construct the longest proper prefix which is also suffix: lps[] with size M = s.size().
the length of the last longest proper prefix is lps[M-1]. The string repeating of sub string only when:
1. lps[M-1] != 0, and
2. lps[M-1]%(M-lps[M-1]) == 0, and the non-repeating substr is s[0 ... M-lps[M-1]-1].
    bool repeatedSubstringPattern(string s) {
        int len = 0, i = 1, M = s.size();
        vector<int> lps(M, 0);
        while(i<M) {
            if(s[len] == s[i]) lps[i++] = ++len;
            else {
                if(len != 0) len = lps[len-1];
                else lps[i++] = 0;
            }
        }
        return lps[M-1] && lps[M-1]%(M-lps[M-1]) == 0;
    }
Solution 1. Shift T chars to the end of string and compare.

    bool repeatedSubstringPattern(string str) {

        string shiftedStr;

        int N = str.size();

        for(int T=1; T <= N/2; T++) {

            if(N%T == 0) {

                shiftedStr = shiftStr(str, T);

                if(str == shiftedStr) return true;

            }

        }

        return false;

    }

    string shiftStr(string& str, int T) {

        string ret = str.substr(T);

        ret += str.substr(0,T);

        return ret;

    }

Solution 2. A naive solution. Assume there are K parts of substr for s, and the size for each part is T. Check T chars K times to see if they are equal.
    bool repeatedSubstringPattern(string s) {
        int N = s.size();
        for(int T=1; T<=N/2; T++) {
            if(N%T != 0) continue;
            int K = N/T;
            int k;
            for(k=1; k<K; k++) {
                if(s.substr(0, T) != s.substr(k*T, T)) break;
            }
            if(k==K) return true;
        }
        return false;
    }