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