Skip to content

Instantly share code, notes, and snippets.

@pwittchen
Created March 30, 2014 15:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pwittchen/9874844 to your computer and use it in GitHub Desktop.
Save pwittchen/9874844 to your computer and use it in GitHub Desktop.
Implementation of Knuth-Morris-Pratt (KMP) algorithm in Java for searching occurences of a specific word in a given string.
public class Main {
public static void main(String args[]) {
String givenString = "ABC ABCDAB ABCDABCDABDE";
String searchedString = "ABCDABD";
int givenStringLetterPosition = 0;
int searchedStringLetterPosition = 0;
int foundAt = -1;
while (givenStringLetterPosition < givenString.length()) {
if (givenString.charAt(givenStringLetterPosition) == searchedString.charAt(searchedStringLetterPosition)) {
if(searchedStringLetterPosition == 0) {
foundAt = givenStringLetterPosition;
}
searchedStringLetterPosition++;
givenStringLetterPosition++;
if(searchedStringLetterPosition == searchedString.length()) {
System.out.println("String found at " + foundAt + " position.");
break;
}
} else {
searchedStringLetterPosition = 0;
foundAt++;
givenStringLetterPosition = foundAt;
if(givenString.length() == givenStringLetterPosition) {
System.out.println("String was not found.");
break;
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment