###### tags: `Leetcode` `easy` `python` `c++` `string` `Top 100 Liked Questions`

# 459. Repeated Substring Pattern

## [題目連結:] https://leetcode.com/problems/repeated-substring-pattern/description/

## 題目:

## 解題想法:
* 此題為判斷字串S，是否能由比他小的子字串構成

* 對於字串須知:
* python
* 字串*n= (字串)(字串)....n個
* ex: abc*3=abcabcabc
* C++:
* 用累加

* 此題想法為:
* 遍歷從頭到len(s)/2的所有距離i
* 如果此距離i為len(s)的因子，表示有機會成為子字串
* 將其position 0~i的子字串重複 len(s)/i次，判斷是否與s相等

## Python:

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        #字串*n= (字串)(字串)....n個
        #abc*3=abcabcabc
        n=len(s)
        for i in range(1, n//2+1):#subStr長度為1至s的一半
            if n%i==0: #是倍數
                subStr=s[:i]
                if subStr*(n//i) == s:
                    return True
        return False

## C++:

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n=s.size();
        for (int i=1; i<=n/2; i++){
            if (n%i==0){
                string subStr= "";
                //重複次數
                int time=n/i;
                for (int j=0; j<time; j++){
                    subStr += s.substr(0,i); //從頭數i個
                }
                if (subStr==s) return true;
            }
        }
        return false;
    }
};