459. 重复的子字符串
题目链接:459. 重复的子字符串
题目描述
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
思路分析
可以根据kmp算法的next数组的性质来做这一个题目,next[len-1]+1表示字符串s的最长公共前后缀长度,len-(next[len-1]+1)表示重复的子串长度,如果能被len整除,那么就是。
代码实现
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int len=s.size();
vector<int>next(len,-1);
for(int i=1,j=-1;i<len;i++)
{
while(j>-1&&s[i]!=s[j+1])j=next[j];
if(s[i]==s[j+1])j++;
next[i]=j;
}
if(next[len-1]!=-1&&len%(len-next[len-1]-1)==0)
return true;
return false;
}
};