LeetCode 459. Repeated Substring Pattern，leetcoderepeated

LeetCode 459. Repeated Substring Pattern，leetcoderepeated

459. 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.)

题目内容：
题目给出一个字符串，让我们判断这个字符串是否可以通过某个子字符串重复拼接重构出来。

解题思路：
因为如果存在这样的一个子串，那么这个子串的第一个字符肯定是s[0]。所以我先找出s中所有与s[0]相同的字符的位置，其实这里只要遍历原字符串的一半，因为这个子串最多也就是原字符串的一半。
那么遍历从小到大遍历这些位置的索引，每遍历到一个索引，都可以算出这个子串的长度，假如这个位置是i，那么可以判断s[0, …, i]与s[0 + i, …, i + i], s[0 + 2i, …, i + 2i]…如果都相同那么说明是存在这样的一个子串的，否则就继续往后遍历，知道遍历完所有可能的索引。

代码：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        if (s.size() <= 1) return false;
        vector<int> char2pos;
        int length = s.size();
        for (int i = 0; i < length; i++) {
            if (s[i] == s[0] && i <= length / 2) char2pos.push_back(i);
        }
        vector<int>::iterator it = char2pos.begin() + 1;
        while (it != char2pos.end()) {
            if (length % (*it) == 0) {
                int subLength = *it;
                int subCnt = length / (subLength);
                bool flag = true;
                for (int i = 1; i < subCnt && flag; i++) {
                    for (int m = 0; m < *it && flag; m++) {
                        if (s[m] != s[m + i * subLength]) flag = false;
                    }   
                }
                if (flag) return flag;
            }
            it++;
        }
        return false;
    }
};