Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple Explanation And Implementation Of Knuth-Morris-Pratt (KMP) Algorithm For String Search
import java.util.ArrayList;
import java.util.List;
public class KMP {
public static final int NOT_FOUND_INDEX = -1;
public static void main(String args[]){
System.out.println("**************** Knuth-Morris-Pratt *****************");
String text = "abcabac";
String pattern = "abac";
long initialTime = System.nanoTime();
int index = findPatternInText(pattern, text);
long finalTime = System.nanoTime();
if(index == NOT_FOUND_INDEX)
System.out.println("Pattern is not find in the text");
else
System.out.println("Successful! Pattern found at index "+index);
System.out.println("Time taken for matching "+(finalTime - initialTime));
}
private static int findPatternInText(String pattern, String text) {
int index = NOT_FOUND_INDEX;
int patternLength = pattern.length();
int textLength = text.length();
char[] textCharArray = text.toCharArray();
char[] patternArray = pattern.toCharArray();
int[] suffixArray = generateSuffixArray(patternLength, pattern);
int i = 0;
boolean isMatched = true;
int j = 0;
while(j < patternLength && i < textLength){
if(textCharArray[i] == patternArray[j]){
j = j + 1;
i =i + 1;
} else{
int newIndex = i - j + 1;
isMatched = false;
j = j - 1;
if (j < 0)
j = 0;
j = suffixArray[j];
if(j==0)
i =newIndex;
else
i = i + 1;
}
if(j == patternLength) {
isMatched = true;
}
}
if(isMatched)
index = i - patternLength;
return index;
}
private static int[] generateSuffixArray(int patternLength, String pattern) {
int[] suffixArray = new int[patternLength];
char[] patternArray = pattern.toCharArray();
int i = 1;
while(i < patternLength){
for(int j = 0; j < patternLength; j++){
if((i < patternLength) && (patternArray[i] == patternArray[j])){
suffixArray[i] = j + 1;
i = i + 1;
} else{
i = i + 1;
break;
}
if(i == patternLength - 1)
break;
}
}
return suffixArray;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.