题目描述

459. 重复的子字符串

思路

这个题做的时候卡住了，看了答案才明白。

这道题给了我们一个字符串，问其是否能拆成n个重复的子串。那么既然能拆分成多个子串，那么每个子串的长度肯定不能大于原字符串长度的一半，因此周期t的取值范围是[1, len/2], 且len % t == 0。
有了以上思路，暴力解法就是，在t的范围内去枚举合适的t值，并验证t是不是这个字符串的周期。

代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.size();
        int i;
        for (int t = 1; t <= len/2; t++) {
            if (len % t == 0) {
                for (i = t; i < len && s[i]==s[i%t]; i++);
                if (i == len) return true;
            }
        }
        return false;
    }
};