LeetCode459 重复的子字符串
前言
题目： 459. 重复的子字符串
文档： 代码随想录——重复的子字符串
编程语言： C++
解题状态： 没思路…
思路
第一种思路就是，当一个字符串由重复子字符串构成时，将相同的这两个字符串拼在一起时，内部也会出现相同的字符串。
第二种思路就是KMP算法。
代码
方法一：拼接法
class Solution {
public:bool repeatedSubstringPattern(string s) {string t = s + s;t.erase(t.begin());t.erase(t.end() - 1);if (t.find(s) != std::string::npos) return true;return false;}
};
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)
方法二：KMP算法
class Solution {
public:void getNext(int* next, const string& s) {next[0] = -1;int j = -1;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;}
};
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)