3
\$\begingroup\$

My implementation of Knuth Morris Pratt algorithm. Looking forward for code review comments. Let me know of there is a better way to implement this algorithm.

import static org.junit.Assert.*;

import org.junit.Test;

public class IsPatternASubString {

    public static boolean isSubString(String s, String p){

        int sIndex = 0;
        int pIndex = 0;
        boolean matchStarted = false;

        while(sIndex < s.length()-1){

            if(s.charAt(sIndex) == p.charAt(pIndex)){
                //Are in the middle of matching process and just getting started
                matchStarted = (pIndex == 0) ? true : matchStarted;

                //Increment both index pointers
                sIndex++;
                //If last char of pattern match exit returning true
                if(pIndex == p.length()-1)
                    return true;
                pIndex++;
            }else{
                //Check if you are broken in the mid way while a matching started
                //If not in stop mid way then just incr sIndex and continue
                if(!matchStarted)
                    sIndex++;
                else{
                    String suffixPrefix = isSuffixIsAlsoAPrefix(p.substring(0, pIndex));
                    if(suffixPrefix != null){
                        pIndex = suffixPrefix.length();
                    }else{
                        //Reset match found flag and pIndex - start from O index of pattern
                        pIndex = 0;
                        matchStarted = false;
                    }
                }
            }
        }
        return false;
    }

public static String isSuffixIsAlsoAPrefix(String input){

        if(input == null || input.length() == 1)
            return null;

        int mid = input.length()/2;
        int left = mid-1;
        int right = input.length()-1;
        int matchCharCount = -1;

        while(left >= 0){
            if(input.charAt(left) == input.charAt(right)){
                matchCharCount = (matchCharCount == -1) ? left+1 : matchCharCount;
                left--;
                right--;
            }else{
                matchCharCount = -1;
                left--;
            }
        }
        return (matchCharCount != -1) ? input.substring(0, matchCharCount) : null;
    }

    @Test
    public void testValidInput_1(){
        String s = "ABCBABCBABDO";
        String p = "BABD";
        assertTrue(isSubString(s, p));
    }

    @Test
    public void testValidInput_2(){
        String s = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
        String p = "AAAAA";
        assertTrue(isSubString(s, p));
    }

    @Test
    public void testFailure(){
        String s = "BBBBBBBBBBBBBBBB";
        String p = "AAAA";
        assertFalse(isSubString(s, p));
    }

    @Test
    public void testValidInput_3(){
        String s = "BBBBBBBBBBBBBBBBCDEFBBBBBCDEFGHBBB";
        String p = "BBBCDEFG";
        assertTrue(isSubString(s, p));
    }

}
\$\endgroup\$
3
  • \$\begingroup\$ Document/comment your code. \$\endgroup\$
    – greybeard
    Aug 22 '17 at 7:12
  • \$\begingroup\$ I don't quite see KMP here: That builds a table upfront, you check for (true) suffix == prefix "on demand" (good for start-up time), but repeatedly (bad for worst case performance - I don't see any "caching"). Please argue how this is KMP (e.g., by giving a reference where this is presented as KMP). \$\endgroup\$
    – greybeard
    Aug 22 '17 at 7:27
  • \$\begingroup\$ On second thoughts: you started out using a test framework (great!) - how about including a "reference"/3rd party implementation, some large and some huge test cases, and use a microbenchmarking framework to check on resource usage? And why is this tagged regex? \$\endgroup\$
    – greybeard
    Aug 22 '17 at 7:33
5
\$\begingroup\$

Bug #1

If the pattern matches to the end of the string, your function returns false:

String s = "ABC";
String p = "ABC";
System.out.println(isSubString(s, p));

false

Bug #2

Your function isSuffixIsAlsoAPrefix() is off. Given a suffix of "ABCDAC", it returns "A" which is incorrect. This leads to the following failure:

String s = "ABCDACBCDACGX";
String p = "ABCDACG";
System.out.println(isSubString(s, p));

true

Not a true KMP implementation

Even if your code were correct, isSuffixIsAlsoAPrefix() takes \$O(m)\$ time which causes the whole algorithm to take \$O(n*m)\$ time, where \$n\$ is the length of the string and \$m\$ is the length of the pattern. A real KMP implementation would build a partial match table first, so that instead of calling isSuffixIsAlsoAPrefix() on a mismatch, it would instead look up the new value of pIndex from the table. This leads to an overall time of \$O(n+m)\$.

I'm wondering how you came up with your algorithm, because it doesn't resemble any Knuth Morris Pratt implementation that I've ever seen.

\$\endgroup\$
1
  • \$\begingroup\$ A real KMP implementation would build a jump table first not quite sure if it was admissible to build that lazily/implicitly (and still call the result KMP). \$\endgroup\$
    – greybeard
    Aug 22 '17 at 7:35
4
\$\begingroup\$

First off, I'm unfamiliar with the KMP algorithm, but that may be an advantage :)

Formatting

It's usually a good idea to adhere to the common code formatting standards for Java. This includes having spaces around keywords, brackets and operators and also using bracket blocks even when you only have one statement:

if (pIndex == p.length() - 1) {
  return true;
}

Code cleaup/readablity

The code could do with some minor changes to make it a bit more readable. For example here:

sIndex++;
if(pIndex == p.length()-1)
    return true;
pIndex++;

could actually have the increments together. Either:

if (pIndex == p.length()-1)
    return true;

sIndex++;
pIndex++;

or to avoid the subtraction of 1:

sIndex++;
pIndex++;

if (pIndex == p.length())
    return true;

Another small thing:

matchStarted = (pIndex == 0) ? true : matchStarted;

could be written as:

matchStarted = pIndex == 0 || matchStarted;

Also avoid negations in the conditions of if/else blocks and instead switch the two blocks. For example instead of:

if (!matchStarted) {
  // Do A
} else {
  // Do B
}

do:

if (matchStarted) {
  // Do B
} else {
  // Do A
}

Comments

For me who doesn't know KMP the comments are mostly pointless. Either they just describe what the code is doing anyway:

//Increment both index pointers

Or they don't seem to make sense:

//Are in the middle of matching process and just getting started

How can one be in the middle of the process and just getting started at the same time? Maybe I'm just missing some context. Try having the comments actually describe how the algorithm works.


isSuffixIsAlsoAPrefix

Here the most work could be done. It begins with the name which starts with is... which normally indicates that it returns a boolean, but it doesn't. Also the name doesn't help me understand what it does. Maybe it's again me missing context.

You also should avoid using null when ever you can. In this case you are using null when you could just be using an empty string, because you are only using the length of the result and have a hard coded 0 where you could just use the length of the empty string, which is 0 anyway. It could be:

pIndex  = isSuffixIsAlsoAPrefix(p.substring(0, pIndex)).length();
if (pIndex == 0) {
    matchStarted = false;
}

This leads to the next point: Since you are just using the length of the return value, which you are calculating in the method anyway as matchCharCount, it would make sense to return that instead directly. That way you save the substring operation at the end, which is quite expensive.

Speaking of expensive substring operations: You should also consider not doing the substring when calling isSuffixIsAlsoAPrefix and instead pass the complete string and pIndex as a second parameter, and use the value of pIndex inside the method instead of the string length.

And finally I believe it's not necessary to set matchCharCount to -1 but use 0, which would remove the condition at the end. So at the end the method could look like this:

public static int isSuffixIsAlsoAPrefix(String input, int length) {

    // Changed the check to include 0 length inputs, too.
    // Dropped the null check, because in that case the algorithm 
    // would already have failed much earlier.
    if (length <= 1) {
        return 0;
    }

    int mid = length / 2;
    int left = mid - 1;
    int right = length - 1;
    int matchCharCount = 0;

    while (left >= 0) {
        if (input.charAt(left) == input.charAt(right)) {
            matchCharCount = (matchCharCount == 0) ? left + 1 : matchCharCount;
            right--;
        } else {
            matchCharCount = 0;
        }
        left--;
    }

    return matchCharCount;
}
\$\endgroup\$
1
  • \$\begingroup\$ unfamiliar with [KMP], but that may be an advantage - looks that way: this is more of a review and less upset about KMP botched up. ("Our" favourite algorithms are getting old (, too).) \$\endgroup\$
    – greybeard
    Aug 22 '17 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.