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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
public int strStr(String hayStack, String needle) {
if (needle.length() > hayStack.length()) {
return -1;
}
int[] lps = buildLPS(needle);
int ptrOne = 0, ptrTwo = 0;
while (ptrOne < hayStack.length() && ptrTwo < needle.length()) {
if (hayStack.charAt(ptrOne) == needle.charAt(ptrTwo)) {
ptrOne += 1;
ptrTwo += 1;
} else {
if (ptrTwo != 0) {
ptrTwo = lps[ptrTwo - 1];
} else {
ptrOne += 1;
}
}
}
if (ptrTwo == needle.length()) {
return ptrOne - needle.length();
}
return -1;
}
private int[] buildLPS(String needle) {
char[] sArray = needle.toCharArray();
int[] ans = new int[needle.length()];
int index = 0;
for (int i = 1; i < ans.length;) {
if (sArray[i] == sArray[index]) {
ans[i] = index + 1;
index += 1;
i += 1;
} else {
if (index != 0) {
index = ans[index - 1];
} else {
ans[i] = 0;
i += 1;
}
}
}
return ans;
}
}
|
KMP
时间复杂度: O(m + n)
空间复杂度: O(n) n是needle的长度.
