Knuth Morris Pratt Algorithm implementation in Java
Below is the code written to implement the KMP algorithm.
Please let me know if it can further be improved or it needs correction.
/**
* String search using Knuth Morris Pratt algorithm
* @author Nitin
*
*/
public class KMPImpl {
private static String text = "abxabcabcaby";
private static String pattern = "abcaby";
// private static pattern = "aabaabaaa";
public static void main(String[] args) {
int foundAt = kmp(text, pattern);
if(foundAt >= 0)
System.out.println("Match found at position : " + foundAt);
else
System.out.println("Match not Found!!!");
}
private static int[] prefSuffPat(String pattern) {
// Time Complexity : O(n)
// Space Complexity : O(n)
// n : length of pattern
int len = pattern.length();
int j = 0;
int i = 1;
int k = 1;
int[] val = new int[len];
val[0] = 0;
while(i < len) {
if(i < len && pattern.charAt(j) == pattern.charAt(i)) {
val[k] = j+1;
j++;
i++;
k++;
} else if(i < len && pattern.charAt(j) != pattern.charAt(i)) {
if(j == 0) {
val[k] = 0;
i++;
k++;
continue;
}
j = val[j-1];
while(j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
j = val[j-1];
}
if(pattern.charAt(j) == pattern.charAt(i)) {
val[k] = j+1;
j++;
i++;
k++;
} else {
val[k] = 0;
i++;
k++;
}
}
}
return val;
}
private static int kmp(String text, String pattern) {
// Time Complexity : O(m+n)
// Space Complexity : O(n)
// n : length of pattern
// m : length of text
int foundAt = -1;
int[] val = prefSuffPat(pattern);
int lenT = text.length();
int lenP = pattern.length();
int j = 0;
int i = 0;
boolean forward = false;
while(i < lenT && j < lenP) {
if(text.charAt(i) == pattern.charAt(j)) {
if(j == 0) {
foundAt = i;
}
i++;
j++;
forward = false;
} else if(text.charAt(i) != pattern.charAt(j) && !forward) {
if(j > 0)
j = val[j-1];
forward = true;
foundAt = i-j;
} else if(text.charAt(i) != pattern.charAt(j) && forward) {
i++;
}
}
if(j != lenP) {
foundAt = -1;
}
return foundAt;
}
}
Please let me know if it can further be improved or it needs correction.
/**
* String search using Knuth Morris Pratt algorithm
* @author Nitin
*
*/
public class KMPImpl {
private static String text = "abxabcabcaby";
private static String pattern = "abcaby";
// private static pattern = "aabaabaaa";
public static void main(String[] args) {
int foundAt = kmp(text, pattern);
if(foundAt >= 0)
System.out.println("Match found at position : " + foundAt);
else
System.out.println("Match not Found!!!");
}
private static int[] prefSuffPat(String pattern) {
// Time Complexity : O(n)
// Space Complexity : O(n)
// n : length of pattern
int len = pattern.length();
int j = 0;
int i = 1;
int k = 1;
int[] val = new int[len];
val[0] = 0;
while(i < len) {
if(i < len && pattern.charAt(j) == pattern.charAt(i)) {
val[k] = j+1;
j++;
i++;
k++;
} else if(i < len && pattern.charAt(j) != pattern.charAt(i)) {
if(j == 0) {
val[k] = 0;
i++;
k++;
continue;
}
j = val[j-1];
while(j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
j = val[j-1];
}
if(pattern.charAt(j) == pattern.charAt(i)) {
val[k] = j+1;
j++;
i++;
k++;
} else {
val[k] = 0;
i++;
k++;
}
}
}
return val;
}
private static int kmp(String text, String pattern) {
// Time Complexity : O(m+n)
// Space Complexity : O(n)
// n : length of pattern
// m : length of text
int foundAt = -1;
int[] val = prefSuffPat(pattern);
int lenT = text.length();
int lenP = pattern.length();
int j = 0;
int i = 0;
boolean forward = false;
while(i < lenT && j < lenP) {
if(text.charAt(i) == pattern.charAt(j)) {
if(j == 0) {
foundAt = i;
}
i++;
j++;
forward = false;
} else if(text.charAt(i) != pattern.charAt(j) && !forward) {
if(j > 0)
j = val[j-1];
forward = true;
foundAt = i-j;
} else if(text.charAt(i) != pattern.charAt(j) && forward) {
i++;
}
}
if(j != lenP) {
foundAt = -1;
}
return foundAt;
}
}