一、题意
二、思考过程
在一个串中查找是否出现过另外一个串，这是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;i<s.size();i++) { while(j>0&&s[i]!=s[j]) { j=next[j-1]; } if(s[i]==s[j]) { j++; } next[i]=j; } } };
