Created
October 21, 2018 02:40
-
-
Save ericwen229/6d4810aab42253b2c431f53a495cfc73 to your computer and use it in GitHub Desktop.
Java implementation of KMP algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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")); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment