LeetCode459. 重复的子字符串


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;

}
};

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

LeetCode459. 重复的子字符串

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » LeetCode459. 重复的子字符串
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏