题目(easy)
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
思路
移动匹配
1
2
3
4
5
6
7
8
9
| 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(1)。
KMP
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
var repeatedSubstringPattern = function (s) {
if (s.length === 0)
return false;
const getNext = (s) => {
let next = [];
let j = 0;
next.push(j);
for (let i = 1; i < s.length; ++i) {
while (j > 0 && s[i] !== s[j])
j = next[j - 1];
if (s[i] === s[j])
j++;
next.push(j);
}
return next;
}
let next = getNext(s);
if (next[next.length - 1] !== 0 && s.length % (s.length - next[next.length - 1]) === 0)
return true;
return false;
};
|
时间复杂度: O(n)。
空间复杂度: O(n)。
