1. Introduction

The KMP (Knuth-Morris-Pratt) Pattern Matching Algorithm is a linear time complexity algorithm used to find a pattern within a text. The central concept of the KMP algorithm is to use the information from the previous match attempts to avoid unnecessary comparisons in the future.

2. Program Steps

1. Compute the Longest Prefix Suffix (LPS) array for the pattern. The LPS array will store the length of the longest proper prefix which is also a proper suffix.

2. Use the LPS array and the pattern to search for the pattern in the text.

3. If a mismatch is found, use the LPS array to determine the next position to continue the search in the text.

3. Code Program

public class KMPPatternMatching {

    // Compute temporary array to maintain size of suffix which is same as prefix
    private static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int index = 0;
        for (int i = 1; i < pattern.length();) {
            if (pattern.charAt(i) == pattern.charAt(index)) {
                lps[i] = index + 1;
                index++;
                i++;
            } else {
                if (index != 0) {
                    index = lps[index - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // KMP Algorithm to find all occurrence of pattern in text
    public static void KMPMatcher(String text, String pattern) {
        int[] lps = computeLPSArray(pattern);
        int j = 0;
        int i = 0;
        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == pattern.length()) {
                System.out.println("Pattern found at index: " + (i - j));
                j = lps[j - 1];
            } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i++;
            }
        }
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        KMPMatcher(text, pattern);
    }
}

Output:

Pattern found at index: 10

4. Step By Step Explanation

1. The computeLPSArray function calculates the longest prefix which is also a proper suffix for every substring of the pattern.

2. The KMPMatcher function uses the LPS array and the pattern to search for the pattern in the text.

3. When a mismatch occurs between the text and pattern, the algorithm uses the LPS array to skip unnecessary comparisons and continue the search.

4. In the provided main method, the pattern "ABABCABAB" is searched in the text "ABABDABACDABABCABAB". The pattern is found at index 10 in the text.