This is Knuth-Morris-Prat algorithm implementation to check if a pattern is present in a larger text, and if it does the algorithm returns the start index of that pattern, else -1. It starts off by computing Longest Common Prefix array, please refer LCP array, and uses that to efficiently avoid redundant pattern matching. I request that my code be reviewed for implementation and naming conventions. For more context about the question please refer, StrStr()
int knuthMorrisPratt(String text, String pattern) {
if (text == null || pattern == null || text.length() < pattern.length) {
return -1;
}
if (pattern.length() == 0) {
return 0;
}
int[] lcp = computeLongestCommonPrefixArray(pattern);
int i = 0, j = 0;
while (i < text.length() && j != pattern.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
else {
if (j > 0) {
j = lcp[j - 1];
continue;
}
}
i++;
}
return (i - j) <= (text.length() - pattern.length()) ? (i - j) : -1;
}
int[] computeLongestCommonPrefixArray(String pattern) {
int[] lcp = new int[pattern.length()];
int len = 0, i = 1;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lcp[i] = len;
i++;
}
else {
if (len != 0) {
len = lcp[len - 1];
}
else {
lcp[i] = 0;
i++;
}
}
}
return lcp;
}
implementation […] conventions
should include code documentation (see mtj's comment, too) - there even is a standard tool. \$\endgroup\$