459.重复的子字符串

给定一个非空的字符串s，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:

输入: s = "aba"
输出: false
示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。）

枚举法：

如果一个长度为n的字符串s可以由它的一个长度为n'的子串重复多次构成，那么：

1.n一定是n'的倍数；

2.s'一定是s的前缀；

3.对于任意的i€[n',n),有s[i]=s[i-n']。

也就是说，s 中长度为 n ′ 的前缀就是 s ′，并且在这之后的每一个位置上的字符 s[i]，都需要与它之前的第 n ′个字符 s[i−n ′] 相同。因此，我们可以从小到大枚举 n'，并对字符串 s 进行遍历，进行上述的判断。注意到一个小优化是，因为子串至少需要重复一次，所以 n' 不会大于 n 的一半，我们只需要在 [1, n/2] 的范围内枚举 n'即可。

bool repeatedSubstringPattern(char * s){

    int n=strlen (s);

    int flg=0;

    for (int i=1;i<=n/2;i++)

    {

        if (n%i==0)

        {

            flg=true;

        }

        for (int j=i;j

        {

            if (s[j]!=s[j-i])

            {

                flg=false;

            }  

        }

        if (flg)

        {

            return true;

        }

    }

    return false;

}

时间复杂度：O（n2）

空间复杂度：O（1）