题目
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab" 输出: True 解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba" 输出: False
示例 3:
输入: "abcabcabcabc" 输出: True 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
解题
方法一：利用KMP算法中的next数组
首先要会KMP算法
next 数组记录的就是最长相同前后缀, 如果 next[-1] != 0，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。
最长相等前后缀的长度为 next[-1]
数组长度为len
如果len % (len - (next[-1] )) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串。
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
(len - (next[-1] )) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。
python解法
class Solution: def repeatedSubstringPattern(self, s: str) -> bool: m = len(s) pnext = [0]*m index=0 j=1 while j<m: if s[index]==s[j]: pnext[j]=index+1 index+=1 j+=1 elif index!=0: index = pnext[index-1] else: j+=1 if m%(m-pnext[-1])==0 and pnext[-1]!=0: return True else: return False
c++解法
class Solution { public: bool repeatedSubstringPattern(string s) { int m=s.size(); int index=0; int i=1; vector<int> pnext(m); while(i<m){ if(s[i]==s[index]){ pnext[i]=index+1; index++; i++; } else if(index!=0){ index=pnext[index-1]; } else{ i++; } } if(m%(m-pnext[m-1])==0&&pnext[m-1]!=0){ return true; } return false; } };
