Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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"));
- }
- }
Add Comment
Please, Sign In to add comment