KMP Algorithm

The KMP (Knuth-Morris-Pratt) Algorithm is a highly efficient string-matching algorithm that was developed jointly by Donald Knuth, Vaughan Pratt, and James H. Morris in 1977. It is primarily used for searching a given pattern within a given text, and it is one of the earliest linear-time string-matching algorithms. The key feature of the KMP algorithm is that it avoids unnecessary comparisons between the pattern and the text by leveraging the information about previously matched characters. This is achieved by preprocessing the pattern to build a longest proper prefix array (also known as the failure function or the prefix function), which helps in determining the next possible starting point for the pattern search in case a mismatch occurs. The KMP algorithm works by iterating through the text one character at a time, attempting to match the pattern to a substring of the text. When a mismatch occurs between the pattern and the text, the algorithm refers to the precomputed prefix array to determine the next possible starting point for the pattern search. This allows the algorithm to skip over sections of the text that have already been determined to not match the pattern, reducing the number of comparisons needed and speeding up the search process. As a result, the KMP algorithm has a worst-case time complexity of O(n + m), where n is the length of the text, and m is the length of the pattern. This makes the KMP algorithm highly efficient in real-world applications, such as searching for specific sequences in DNA, text search in document editors, and string manipulation in programming languages.
package Others;

/**
 * Implementation of Knuth–Morris–Pratt algorithm
 * Usage: see the main function for an example
 */
public class KMP {
    //a working example
    public static void main(String[] args) {
        final String haystack = "AAAAABAAABA";        //This is the full string
        final String needle = "AAAA";                //This is the substring that we want to find
        KMPmatcher(haystack, needle);
    }

    // find the starting index in string haystack[] that matches the search word P[]
    public static void KMPmatcher(final String haystack, final String needle) {
        final int m = haystack.length();
        final int n = needle.length();
        final int[] pi = computePrefixFunction(needle);
        int q = 0;
        for (int i = 0; i < m; i++) {
            while (q > 0 && haystack.charAt(i) != needle.charAt(q)) {
                q = pi[q - 1];
            }

            if (haystack.charAt(i) == needle.charAt(q)) {
                q++;
            }

            if (q == n) {
                System.out.println("Pattern starts: " + (i + 1 - n));
                q = pi[q - 1];
            }
        }
    }

    // return the prefix function
    private static int[] computePrefixFunction(final String P) {
        final int n = P.length();
        final int[] pi = new int[n];
        pi[0] = 0;
        int q = 0;
        for (int i = 1; i < n; i++) {
            while (q > 0 && P.charAt(q) != P.charAt(i)) {
                q = pi[q - 1];
            }

            if (P.charAt(q) == P.charAt(i)) {
                q++;
            }

            pi[i] = q;

        }
        return pi;
    }
}

LANGUAGE:

DARK MODE: