LintCode 1227: Repeated Substring Pattern，lintcoderepeated

LintCode 1227: Repeated Substring Pattern，lintcoderepeated

1227. Repeated Substring Pattern
      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.)

思路：取pattern size从1到len/2，然后原字符串分段与pattern比较。代码如下。注意去掉不可能的情况，这样可以节省时间。

class Solution {
public:
    /**
     * @param s: a string
     * @return: return a boolean
     */
    bool repeatedSubstringPattern(string &s) {
        int len = s.size();
        if (len & 0x1) return false;
        int halfLen = len >> 1;
        for (int i = 1; i <= halfLen; ++i) {
            string seg = s.substr(0, i);
            if (len % i != 0) continue;    //去掉不可能的情况
            int multi = len / i;
            bool isRepeated = true;
            for (int j = 0; j < multi; ++j) {
                if (s.substr(j * i, i) != seg) {
                    isRepeated = false;
                    break;
                }
            } 
            if (isRepeated) return true;
        }
        return false;
    } 
};