-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStrStr.java
More file actions
77 lines (73 loc) · 2.41 KB
/
Copy pathStrStr.java
File metadata and controls
77 lines (73 loc) · 2.41 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
// KMP algorithm:
// http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
public class StrStr{
public int[] longestPreSuffix(String needle){
// assume needle is not null, nor empty
int[] table = new int[needle.length()];
table[0] = 0;
for(int i = 1; i < needle.length(); i++){
int index = table[i-1];
while(needle.charAt(index) != needle.charAt(i) && index > 0){
index = table[index - 1];
}
if(needle.charAt(index) == needle.charAt(i)){
table[i] = index + 1;
}else{
table[i] = 0;
}
}
return table;
}
public int maxMatch(String haystack, int i, String needle, int preMatched){
int j = preMatched;
i += preMatched;
while(i < haystack.length() && j < needle.length()){
if(haystack.charAt(i) == needle.charAt(j)){
i++;
j++;
} else {
return j;
}
}
return j;
}
public int strStr(String haystack, String needle) {
if(haystack == null || needle == null || needle.length() == 0)
return 0;
int hLen = haystack.length();
int nLen = needle.length();
if(hLen < nLen)
return -1;
// construct table
int[] table = longestPreSuffix(needle);
// start from i = 0, matched = 0
// if(hay.length - i < ne.length) return -1
// n = longestmatch(hay, i, ne, matched)
// if(n == ne.length) return 1
// if n = 0 i++
// matched = table[n-1]
// i += (n - matched)
int i = 0, preMatched = 0;
while(true){
if(hLen - i < nLen)
return -1;
int numMatched = maxMatch(haystack, i, needle, preMatched);
if(numMatched == 0){
i++;
} else if (numMatched == nLen){
return i;
} else {
preMatched = table[numMatched - 1];
i += (numMatched - preMatched);
}
}
}
public static void main(String[] argvs){
StrStr s = new StrStr();
System.out.println(s.strStr("bacbababaabcbab", "ababa"));
for(int i: s.longestPreSuffix("xybxyaxybxyb")){
System.out.print(i + " ");
}
System.out.println();
}
}