Is given pattern a subString of given input string? KMP implementation 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 &lt; 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 &gt;= 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));
    }

}
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.