-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathLeetCode_00028.java
More file actions
67 lines (62 loc) · 1.89 KB
/
LeetCode_00028.java
File metadata and controls
67 lines (62 loc) · 1.89 KB
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package com.github.jerring.leetcode;
public class LeetCode_00028 {
// public int strStr(String haystack, String needle) {
// return haystack.indexOf(needle);
// }
// public int strStr(String haystack, String needle) {
// if (needle.length() == 0) {
// return 0;
// }
// int max = haystack.length() - needle.length();
// for (int i = 0; i <= max; ++i) {
// // 找到第一个相等的字符
// if (haystack.charAt(i) == needle.charAt(0)) {
// int j = i + 1;
// for (int k = 1; k < needle.length()
// && haystack.charAt(j) == needle.charAt(k); ++k, ++j);
// // 找到整个字符串就返回
// if (j == i + needle.length()) {
// return i;
// }
// }
// }
// return -1;
// }
// KMP
public int strStr(String haystack, String needle) {
int[] next = getNextArray(needle);
int i = 0;
int j = 0;
while (i < haystack.length() && j < needle.length()) {
if (haystack.charAt(i) == needle.charAt(j)) {
++i;
++j;
} else if (next[j] != -1) {
j = next[j];
} else {
++i;
}
}
return j == needle.length() ? i - j : -1;
}
private int[] getNextArray(String s) {
if (s.length() <= 1) {
return new int[] { -1 };
}
int[] next = new int[s.length()];
next[0] = -1;
next[1] = 0;
int len = 0;
int i = 2;
while (i < s.length()) {
if (s.charAt(i - 1) == s.charAt(len)) {
next[i++] = ++len;
} else if (len > 0) {
len = next[len];
} else {
next[i++] = 0;
}
}
return next;
}
}