> For the complete documentation index, see [llms.txt](https://dfine.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dfine.gitbook.io/leetcode/459.repeated_substring_pattern.md).

# 459.Repeated Substring Pattern

**459.Repeated Substring Pattern**

难度:Easy

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

找出是否是循环字串，可以先统计26个字母出现的频次，然后找到所有出现次数不为0的最小公约数(至少为2)，即最少的循环次数。然后比较。

```
lass Solution {
int max_factor(int a, int b)
{
    if(a<b) swap(a,b);
    if(b==0) return a;
    for(int i=2;i<=b;i++)
        if(a%i==0 && b%i ==0 )return i;
    return 1;
}
public:
    bool repeatedSubstringPattern(string s) {
        vector<int>alpha(26,0);
        for(auto c:s)
            ++alpha[c-'a'];
        int len=0;
        for(auto i:alpha)
//        {
            len=max_factor(len,i);
     //       cout<< i<<" ";
   //     }
   //     cout<<endl;
  //     cout<< len << " "<<endl;

        if(len == 1  )return false;
        
        int one_size=s.length()/len;
//  cout<<one_size<<endl;
     for(int j=0;j<one_size;j++)
            for(int i=1;i<len;i++)
                if(s[i*one_size+j] !=s[j]) return false;
        return true;
        
    }
};
```

> 执行用时 :28 ms, 在所有 C++ 提交中击败了97.08%的用户\
> 内存消耗 :11.5 MB, 在所有 C++ 提交中击败了94.35%的用户