重复的子字符串
提取小串做模式组，再进行KMP匹配
（复杂度高）
class Solution { public: void getNext(int* next, const string& s) { int j = -1; next[0] = j; for (int i = 1; i < s.size(); i++) { while (j >= 0 && s[i] != s[j + 1]) { j = next[j ]; } if (s[i] == s[j + 1]) j++; next[i] = j; } } bool repeatedSubstringPattern(string s) { string substr; if(s.size()==0) return false; for (int cur = 0; cur < s.size(); cur++)//循环找小串 { if (s[cur] != substr[0]) substr += s[cur]; //文字串中和小串第一个不相同的加入小串 else //发现文字串有和小串开头相同的 { int *next = new int[substr.size()]; getNext(next, substr); int j = -1; for (int i = 0; i < s.size(); i++) //kmp { if ( s[i] != substr[j + 1])//发现有匹配失败的，直接跳出给小串加长 { j = next[j ];//应该是没啥用，从kmp复制过来的。这个题不涉及退回，发现错误直接跳出了 break; } if (s[i] == substr[j + 1]) { j++; } if (i == (s.size() - 1) && j == (substr.size() - 1)) //发现匹配成功，并且匹配的成功最后一个就是整个文字串的最后一个。返回成功 { return true; } if (j == substr.size() - 1) { j = -1; } } delete[] next; substr += s[cur]; } } return false; } };
直接KMP算法
class Solution { public: void getNext(int* next, const string& s) { int j = -1; next[0] = j; for (int i = 1; i < s.size(); i++) { while (j >= 0 && s[i] != s[j + 1]) { j = next[j ]; } if (s[i] == s[j + 1]) j++; next[i] = j; } } bool repeatedSubstringPattern(string s) { if (s.size() == 0) { return false; } int *next = new int[substr.size()]; //计算整个文字串的next数组，如果文字串是循环的，一个循环next都是-1，之后的从0开始递增。next的最后一位的值=（循环次数-1）*循环体长度 -1 getNext(next, s); int len = s.size(); //文字串的长度减去next数组最后一位+1 ，得到是循环体长度 // 如果next数组最后一位不是-1（意味着之前匹配成功） ， 并且文字串长度对循环体长度可以整除 if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) { delete[] next; return true; } delete[] next; return false; } };
二刷
移动匹配法
class Solution { public: bool repeatedSubstringPattern(string s) { string tmp = s + s; tmp.erase(0,1); tmp.erase(tmp.size()-1,1); if(tmp.find(s) == -1) return false; else return true; } };
KMP
class Solution { public: void getnext(int *next , const string &s) { int j=-1; next[0] = j; for(int i=0 ; i<s.size() ;i++) { while(j>=0 && s[i] != s[j+1]) j = next[j]; if(s[i] == s[j+1]) j++; next[i] = j; } return ; } bool repeatedSubstringPattern(string s) { int j=-1; int next[s.size()]; getnext(next ,s); if(next[s.size()-1] != -1 && s.size() % ( s.size() - ( next[s.size()-1] -1 ) ) ==0 ) return true; else return false; } };
