Simple Explanation And Implementation Of Knuth-Morris-Pratt (KMP) Algorithm For String Search

KMP.java

import java.util.ArrayList;
import java.util.List;

public class KMP {

    public static final int NOT_FOUND_INDEX = -1;

    public static void main(String args[]){
        System.out.println("**************** Knuth-Morris-Pratt *****************");

        String text = "abcabac";
        String pattern = "abac";
        long initialTime = System.nanoTime();
        int index = findPatternInText(pattern, text);
        long finalTime = System.nanoTime();
        if(index == NOT_FOUND_INDEX)
            System.out.println("Pattern is not find in the text");
        else
            System.out.println("Successful! Pattern found at index "+index);
        System.out.println("Time taken for matching "+(finalTime - initialTime));
    }

    private static int findPatternInText(String pattern, String text) {
        int index = NOT_FOUND_INDEX;
        int patternLength = pattern.length();
        int textLength = text.length();
        char[] textCharArray = text.toCharArray();
        char[] patternArray = pattern.toCharArray();

        int[] suffixArray = generateSuffixArray(patternLength, pattern);

        int i = 0;
        boolean isMatched = true;
        int j = 0;
        while(j < patternLength && i < textLength){
            if(textCharArray[i] == patternArray[j]){
                j = j + 1;
                i =i + 1;
            } else{
                int newIndex = i - j + 1;
                isMatched = false;
                j = j - 1;
                if (j < 0)
                    j = 0;
                j = suffixArray[j];
                if(j==0)
                    i =newIndex;
                else
                    i = i + 1;
            }

            if(j == patternLength) {
                isMatched = true;
            }

        }
        if(isMatched)
            index = i - patternLength;

        return index;
    }

    private static int[] generateSuffixArray(int patternLength, String pattern) {
        int[] suffixArray = new int[patternLength];
        char[] patternArray = pattern.toCharArray();
        int i = 1;
        while(i < patternLength){
            for(int j = 0; j < patternLength; j++){
                if((i < patternLength) && (patternArray[i] == patternArray[j])){
                    suffixArray[i] = j + 1;
                    i = i + 1;

                } else{
                    i = i + 1;
                    break;
                }

                if(i == patternLength - 1)
                    break;
            }

        }

        return  suffixArray;
    }
}