这道题不会，看了卡哥思路，卡哥提供了三种方法。
方法一：暴力解法
自己写的代码：
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int len = 1; len <= n / 2; ++len)
{
if (n % len != 0)
continue;
int k = 0;
bool flag = true;
for (int i = 0; i < n; ++i)
{
if (s[k++] != s[i])
{
flag = false;
break;
}
if (k == len)
k = 0;
}
if (flag)
return true;
}
return false;
}
};
类似的思路，但是更好的代码：
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int len = 1; len <= n / 2; ++len)
{
if (n % len != 0)
continue;
int k = 0;
bool flag = true;
for (int i = 0; i < n; ++i)
{
if (s[k] != s[i])
{
flag = false;
break;
}
k = (k + 1) % len;
}
if (flag)
return true;
}
return false;
}
};
主要是这句代码k = (k + 1) % len;的处理比较好。
方法二：移动匹配
卡哥思路里面有证明，证明了充分性和必要性。
跟着卡哥代码写了一下：
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string t = s + s;
t.erase(t.begin());
t.erase(t.end() - 1);
if (t.find(s) != string::npos) return true;
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[s.size()];
getNext(next, s);
int len = s.size();
if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0)
return true;
return false;
}
};