How to implement KMP algorithm using java

How to use Java to implement the KMP algorithm

The KMP algorithm (Karp-Miller-Rosenberg algorithm) is a string matching algorithm that uses already matched information to Avoid unnecessary matching to improve matching efficiency. The KMP algorithm is an efficient algorithm when dealing with large-scale text and pattern string matching. This article will introduce how to use Java to implement the KMP algorithm and give specific code examples.

1. Principle of KMP algorithm
1.1. Prefix function
The core idea of ​​KMP algorithm is to use the prefix function (also called the longest common prefix and suffix) to handle the pattern string when the matching fails. Jump.

The prefix function is an array pi, where pi[i] represents the length of the longest true prefix and the longest true suffix of the string ending with the i-th character among the first i characters of the pattern string. For example, the prefix function of the pattern string "ababaca" is [0, 0, 1, 2, 3, 0, 1].

1.2. Main steps of KMP algorithm
The main steps of KMP algorithm are as follows:
1) Calculate the prefix function of the pattern string;
2) Match in the text string, use the prefix function to Handle match failure situations.

2. KMP Algorithm Implementation
Below we introduce how to use Java to implement the KMP algorithm.

public class KMP {
    public static int[] computePrefixFunction(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];
        int k = 0;
        for (int i = 1; i < m; i++) {
            while (k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
                k = pi[k - 1];
            }
            if (pattern.charAt(k) == pattern.charAt(i)) {
                k++;
            }
            pi[i] = k;
        }
        return pi;
    }

    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] pi = computePrefixFunction(pattern);
        int q = 0;
        for (int i = 0; i < n; i++) {
            while (q > 0 && pattern.charAt(q) != text.charAt(i)) {
                q = pi[q - 1];
            }
            if (pattern.charAt(q) == text.charAt(i)) {
                q++;
            }
            if (q == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String text = "ababababacaba";
        String pattern = "bac";
        int index = search(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

In the above code, the computePrefixFunction function is used to calculate the prefix function of the pattern string, and the search function is used to match in the text string. In the main function, we can see how to call the search function to perform pattern matching and output the matching results.

3. Summary
By using the KMP algorithm, we can effectively perform string matching operations. This article introduces the principle of the KMP algorithm and how to use Java to implement the KMP algorithm. I hope this article will help you learn and understand the KMP algorithm.

The above is the detailed content of How to implement KMP algorithm using java. For more information, please follow other related articles on the PHP Chinese website!