2
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Review! This question is incomplete. To help reviewers give you better answers, please add sufficient context to your question. The more you tell us about what your code does and what the purpose of doing that is, the easier it will be for reviewers to help you. See also this meta question. \$\endgroup\$ Commented Feb 16, 2017 at 0:20
  • \$\begingroup\$ As a start: you code totally fails to convey what it is about to the reader. KMP? LCP? WTF? I suggest you start off by renaming you abbrevs to something meaningful and revise the question (as long as there's no answer yet.) \$\endgroup\$ Commented Feb 16, 2017 at 7:09
  • \$\begingroup\$ I find the naming much improved in late revisions (just correct Pratt's name). implementation […] conventions should include code documentation (see mtj's comment, too) - there even is a standard tool. \$\endgroup\$ Commented Feb 16, 2017 at 21:57

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.