【LeetCode 22】459.重复的子字符串

【LeetCode 22】459.重复的子字符串

【LeetCode 22】459.重复的子字符串

文章目录

​​【LeetCode 22】459.重复的子字符串​​​​一、题意​​​​二、思考过程​​​​三、完整代码​​

一、题意

二、思考过程

在一个串中查找是否出现过另外一个串，这是KMP的看家本领。所以这道题依然要使用到KMP。不推荐hash和暴力破解。

【重点】如下：

如果​​next[len-1]!=0​​,说明字符串有最长相同前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。如果​​len%(len-(next[len-1]))==0​​,说明字符串有重复的子字符串。

int len=s.size(); if(next[len-1]!=0&&len%(len-(next[len-1]))==0) { return true; } return false;

三、完整代码

class Solution {public: bool repeatedSubstringPattern(string s) { if(s.size()==0) { return false; } int next[s.size()]; getNext(next,s); //重点 int len=s.size(); if(next[len-1]!=0&&len%(len-(next[len-1]))==0) { return true; } return false; } void getNext(int *next,const string& s) { int j=0; next[0]=0; for(int i=1;i0&&s[i]!=s[j]) { j=next[j-1]; } if(s[i]==s[j]) { j++; } next[i]=j; } }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。