这是一道我没做出来的简单题 5555
学习
方法1:移动匹配
如果一个字符串可以由一个字串重复获得, 那么将两个相同字符串并起来 一定可以在中间再找到该字符串
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;
}
};
方法2:KMP算法 有想到用KMP 不知道该怎么写 就是屑啦
在一个串中是否出现过另一个串 必须想到KMP欸
但是重复子字符串跟KMP又有什么关系捏
如果是由子字符串n重复得到的字符串s,且s由k个n重复得到, 那么s的最大前后缀一定是(k-1)个n,且字符串s的next表中next[s.size() - 1]一定不为0 且 s与k个n的差一定是一个s, 该s就是子字符串, 所以 s.size() % (s.size() - next[s.size() - 1]) == 0
class Solution {
public:
void getNext(int *next, string s)
{
int j = 0; // j指向前缀末尾
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;
}
}
bool repeatedSubstringPattern(string s) {
int next[s.size()];
getNext(next, s);
if (next[s.size() - 1] != 0 && s.size() % (s.size() - next[s.size() - 1]) == 0)
return true;
return false;
}
};