459. Repeated Substring Pattern -E

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

A:

---------------------用了 set 的size要相等。 和 substring的长度可以整除 来加速------------

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        set<char> S;
        for(auto c : s)
        {
            S.insert(c);
        }
        int n = s.length();
        int charCount = S.size();
        // no test until we find all characters
        set<char> smallS;
        for(int i =0;i< n/2 ;++i)// we go at most half of s
        {
            smallS.insert(s[i]);
            if(smallS.size() < charCount)
                continue;
            // now we can test
            int subLen = i+1;
            if( ( n % subLen) != 0 )
                continue;
            // now we can test all 
            string tmp = s.substr(0,subLen);
            int start = i+1;
            while(start <n)
            {
                if(s.substr(start, subLen) == tmp)
                {
                    start += subLen;
                }else{
                    break;
                }
            }
            if(start >= n)
                return true;
        }
        return false;
    }
};