1.问题描述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。
示例 2:
输入: “aba”
输出: False
示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

2.问题分析

本题我的思路：使用kmp算法把字符串各个位置的next数组值求出来，那么此时我们就可以找到最后一个位置的字符，它的next数组值在本题中有及其重要的参考作用，返回false的有几种情况
1.当s.length()==0||s.length()==1
2.当字符串最后一个字符的next数组值为0即kmp[s.length()-1]==0
3.求完next数组后(这里用kmp数组表示所谓的next数组)，n - next[n] 就是子串的长度，需要解答题目只需要 n % (n - next[n]) == 0 即可s.length()%(s.length()-kmp[s.length()-1])!=0

3代码实现

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        if(s.length()==0||s.length()==1)
        return false;
        int t=0;
        int kmp[s.length()];
        kmp[0]=0;
        for(int i=1;i<s.length();i++)
        {
            t=kmp[i-1];
            while(t>0&&s[t]!=s[i])
            t=kmp[t-1];
            if(s[t]==s[i])
            {
                t++;
                kmp[i]=t;
            }
            else
            kmp[i]=0;
        }
        if(s.length()%(s.length()-kmp[s.length()-1])!=0||kmp[s.length()-1]==0)
        return false;
        return true;
        
    }
};