-
Notifications
You must be signed in to change notification settings - Fork 0
/
KMP.java
74 lines (68 loc) · 2.13 KB
/
KMP.java
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
/**
* This code is to conduct pattern matching of given str and pattern
*
* @Author Gyeong - lemidia
*/
public class KMP {
public static void kmp (String str, String pattern) {
int lps[] = LPS(pattern);
int i = 0;
int j = 0;
while (i < str.length()) {
if (str.charAt(i) == pattern.charAt(j)) {
if (j == pattern.length() - 1) {
int foundIdx = i - pattern.length() + 1;
System.out.println("The pattern was found at index " + foundIdx + " of the text.");
i++;
j = lps[j];
} else {
i++;
j++;
}
} else {
if (j == 0)
i++;
else
j = lps[j-1];
}
}
}
// Construct an LPS array that represents proper
// prefix which is also suffix of the given pattern
public static int[] LPS (String pattern) {
int lps[] = new int[pattern.length()];
int i = 1;
int j = 0;
// While less than lps or pattern length
while (i < lps.length) {
if (pattern.charAt(j) == pattern.charAt(i)) {
lps[i] = j + 1;
i++;
j++;
} else {
// There is no more space to go to left
// So, just increment the i's index by 1
if (j == 0)
i++;
// We go to the previous index.
// And look up Longest proper prefix which is
// also suffix of previous string
// And Let this be j
else
j = lps[j-1];
}
}
return lps;
}
public static void main(String[] args) {
String str = "abababacd";
String pattern = "aba";
/*
Output:
The pattern was found at index 0 of the text.
The pattern was found at index 2 of the text.
The pattern was found at index 4 of the text.
*/
kmp(str, pattern);
}
}