Created
January 19, 2017 21:08
-
-
Save deyindra/aeeeb73789a323ba2febf7c4a4e99fc3 to your computer and use it in GitHub Desktop.
KMP for Sub Array Search
This file contains 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
private static <T> int[] computeTemporaryArray(T pattern[]){ | |
int [] lps = new int[pattern.length]; | |
int index =0; | |
for(int i=1; i < pattern.length;){ | |
if(equals(pattern[i],pattern[index])){ | |
lps[i] = index + 1; | |
index++; | |
i++; | |
}else{ | |
if(index != 0){ | |
index = lps[index-1]; | |
}else{ | |
lps[i] =0; | |
i++; | |
} | |
} | |
} | |
return lps; | |
} | |
public static <T> boolean equals(T a, T b){ | |
if(a==null) | |
return (b==null); | |
else | |
return a.equals(b); | |
} | |
/** | |
* KMP algorithm of pattern matching. | |
*/ | |
public static <T> List<Integer> KMP(T []text, T []pattern){ | |
int lps[] = computeTemporaryArray(pattern); | |
int i=0; | |
int j=0; | |
List<Integer> list = new ArrayList<>(); | |
while(i < text.length && j < pattern.length){ | |
if(equals(text[i] , pattern[j])){ | |
i++; | |
j++; | |
}else{ | |
if(j!=0){ | |
j = lps[j-1]; | |
}else{ | |
i++; | |
} | |
} | |
if(j == pattern.length){ | |
list.add(i - pattern.length); | |
j = lps[j-1]; | |
} | |
} | |
return list; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment