题目：
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
代码：
思路1 (暴力算法)：省略
思路2 （移动匹配）：
两个重复的字符串，肯定能组成一个新的s
代码
bool repeatedSubstringPattern(string s) {
string s1 = s + s;
s1.erase(s1.begin());
s1.erase(s1.begin()+(s1.size()-1));
if( s1.find(s) == std::string::npos ) return false;
return true;
}
点击查看代码
class Solution {
public:
void getNext (int* next, const string& s){
next[0] = 0;
int j = 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;
}
}
bool repeatedSubstringPattern(string s) {
int next[s.size()];
getNext(next, s);
int len = s.size();
for(int i = 0 ; i< len ;i++) cout << next[i] << " ";
if(next[len - 1] != 0 && len % (len - next[len-1]) == 0 ) return true;
return false;
}
};