forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStrStrKmp.java
More file actions
126 lines (123 loc) · 2.71 KB
/
StrStrKmp.java
File metadata and controls
126 lines (123 loc) · 2.71 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// Source : https://leetcode.com/problems/implement-strstr/description/
// Inspired by : http://wiki.jikexueyuan.com/project/kmp-algorithm/define.html
// Author : Tianming Cao
// Date : 2018-02-11
/**********************************************************************************
*
* Implement strStr().
*
* Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
*
* Example 1:
*
* Input: haystack = "hello", needle = "ll"
* Output: 2
*
* Example 2:
*
* Input: haystack = "aaaaa", needle = "bba"
* Output: -1
*
**********************************************************************************/
package strStr;
public class StrStrKmp {
/**
* KMP-Algorithm
*/
public int strStr(String haystack, String needle) {
if (haystack == null && needle == null) {
return 0;
}
if (haystack == null && needle != null) {
return -1;
}
if (haystack != null && needle == null) {
return -1;
}
int m = haystack.length();
int n = needle.length();
if (m < n) {
return -1;
}
if (n == 0) {
return 0;
}
int[] nextArray = getNext(needle);
int i = 0;
int j = 0;
while (i < m) {
if (j == -1) {
// If pointer j is in boundary, move i to the right and reset j
i++;
j = 0;
} else {
if (haystack.charAt(i) == needle.charAt(j)) {
// While matching succeess, move both pointer i and pointer j to the right
i++;
j++;
if (j == n) {
return i - n;
}
} else {
/***
* For example:
*
* next: [-1,0,0,0,0,1,2]
*
* i
* ↓
* haystack:BBC ABCDAB ABCDABCDABDE
* j
* ↓
* needle: ABCDABD
*
*
* So the next step is:
*
* i
* ↓
* haystack:BBC ABCDAB ABCDABCDABDE
* j
* ↓
* needle: ABCDABD
*/
j = nextArray[j];
}
}
}
return -1;
}
/**
* Generate the next-array of needle string
*
* For example:
*
* next-array of "ABCDABD" is: [-1,0,0,0,0,1,2]
*
* For letter "D", the longest prefix "AB" is equal to the longest suffix "AB",
* the string "AB"'s length is 2, so letter "D"'s next value is 2.
*/
public int[] getNext(String str) {
int len = str.length();
int[] next = new int[len];
next[0] = -1;
int k = -1;
int j = 0;
while (j < len - 1) {
if (k == -1) {
k = 0;
next[j + 1] = 0;
j++;
} else {
if (str.charAt(j) == str.charAt(k)) {
next[j + 1] = k + 1;
k++;
j++;
} else {
k = next[k];
}
}
}
return next;
}
}