ericwen229
10/21/2018 - 2:40 AM

## Java implementation of KMP algorithm

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"));
}

}
``````