-
Notifications
You must be signed in to change notification settings - Fork 19
/
KMPAlgo.java
101 lines (92 loc) · 3.1 KB
/
KMPAlgo.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
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
package com.forum.java.algos;
public class KMPAlgo {
/**
* Pre processes the pattern array based on proper prefixes and proper
* suffixes at every position of the array
*
* @param ptrn
* word that is to be searched in the search string
* @return partial match table which indicates
*/
public int[] preProcessPattern(char[] ptrn) {
int i = 0, j = -1;
int ptrnLen = ptrn.length;
int[] b = new int[ptrnLen + 1];
b[i] = j;
while (i < ptrnLen) {
while (j >= 0 && ptrn[i] != ptrn[j]) {
// if there is mismatch consider next widest border
j = b[j];
}
i++;
j++;
b[i] = j;
}
// print pettern, partial match table and index
System.out
.println("printing pattern, partial match table, and its index");
System.out.print(" ");
for (char c : ptrn) {
System.out.print(c + " ");
}
System.out.println(" ");
for (int tmp : b) {
System.out.print(tmp + " ");
}
System.out.print("\n ");
for (int l = 0; l < ptrn.length; l++) {
System.out.print(l + " ");
}
System.out.println();
return b;
}
/**
* Based on the pre processed array, search for the pattern in the text
*
* @param text
* text over which search happens
* @param ptrn
* pattern that is to be searched
*/
public void searchSubString(char[] text, char[] ptrn) {
int i = 0, j = 0;
// pattern and text lengths
int ptrnLen = ptrn.length;
int txtLen = text.length;
// initialize new array and preprocess the pattern
int[] b = preProcessPattern(ptrn);
while (i < txtLen) {
while (j >= 0 && text[i] != ptrn[j]) {
System.out.println("Mismatch happened, between text char "
+ text[i] + " and pattern char " + ptrn[j]
+ ", \nhence jumping the value of " + "j from " + j
+ " to " + b[j] + " at text index i at " + i
+ " based on partial match table");
j = b[j];
}
i++;
j++;
// a match is found
if (j == ptrnLen) {
System.out.println("FOUND SUBSTRING AT i " + i + " and index:"
+ (i - ptrnLen));
System.out.println("Setting j from " + j + " to " + b[j]);
j = b[j];
}
}
}
// only for test purposes
public static void main(String[] args) {
KMPAlgo stm = new KMPAlgo();
// pattern
char[] ptrn = "abcabdabc".toCharArray();
char[] text = "abcabdabcabeabcabdabcabd".toCharArray();
System.out.print(" ");
for (char c : text) {
System.out.print(c + " ");
}
System.out.println();
// search for pattern in the string
stm.searchSubString(text, ptrn);
}
}