Java implementation of KMP algorithm
public class KMP {
private final String pattern;
private final int[] next;
public KMP(String _pattern) {
if (_pattern == null) {
throw new IllegalArgumentException("pattern cannot be null");
}
else if (_pattern.isEmpty()) {
throw new IllegalArgumentException("pattern cannot be empty");
}
pattern = _pattern;
next = computeNext(pattern);
}
public String getPattern() {
return pattern;
}
public int firstOccurenceAt(String str) {
return firstOccurenceAt(str, 0);
}
public int firstOccurenceAt(String str, int initPos) {
if (str == null
|| str.isEmpty()) {
return -1;
}
int iStr = initPos;
int iPattern = 0;
while (iStr < str.length() && iPattern < pattern.length()) {
if (iPattern == -1
|| str.charAt(iStr) == pattern.charAt(iPattern)) {
iStr++;
iPattern++;
}
else {
iPattern = next[iPattern];
}
}
if (iPattern == pattern.length()) {
return iStr - pattern.length();
}
else {
return -1;
}
}
private int[] computeNext(String pattern) {
int patternLength = pattern.length();
int[] next = new int[patternLength];
next[0] = -1;
for (int i = 1; i < patternLength; i++) {
// next[0..i-1] has been set properly
// set next[i] properly
char prevChar = pattern.charAt(i - 1);
int potentialMatchPosition = next[i - 1];
while (potentialMatchPosition != -1
&& prevChar != pattern.charAt(potentialMatchPosition)) {
potentialMatchPosition = next[potentialMatchPosition];
}
next[i] = potentialMatchPosition + 1;
}
return next;
}
public static void main(String[] args) {
KMP kmp = new KMP("abcdabd");
System.out.println(kmp.firstOccurenceAt("bbc abcdab abcdabcdabde"));
}
}