Shulou(Shulou.com)06/01 Report--

This article mainly explains "Java how to implement KMP algorithm", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let Xiaobian take you to learn "Java how to implement KMP algorithm"!

KMP algorithm

KMP (Knuth-Morris-Pratt) is an improved string matching algorithm. KMP algorithm solves the problem of high frequency backoff in brute-force matching. KMP algorithm does not need backoff in string position after matching several characters, so it greatly improves efficiency. As shown in the figure:

For example (string "abcabcdef" matches string "abcdef"):

Number of Violent Matches KMP Algorithm Description 1abcabcdef abcdefa and a match 2abcabcdef abcdefabcdef abcdefab and ab match 3abcabcdef abcdefabcdef abcdefabc and abc match 4abcabcdef abcdefabca and abcd do not match, backoff. Violent matching falls back to index 1, i.e."b", KMP algorithm index jumps 3, i.e."a"5abcabcdef abcdef abcdef Violent matching b and a do not match, moves back. KMP algorithm a and a match 6abcabcdef abcdefabcabcdef abcdef brute force match c and a do not match, move back. KMP algorithm ab and ab match 7abcabcdef abcdef abcdef brute force match a and a match. KMP algorithm abc and abc match 8abcabcdef abcdef abcdef brute force match ab and ab match. KMP algorithm abcd and abcd match 9abcabcdef abcdef abcdef brute force match abc and abc match. KMP algorithm abcde and abcde match 10abcabcdef abcdef abcdef brute force match abcd and abcd match. KMP algorithm abcdef and abcdef matching, matching complete 11abcabcdef abcdef abcdef brute force matching abcde and abcde matching. KMP algorithm matching complete 12abcabcdef abcdef abcdef violence matching abcd and abcd matching, matching complete. KMP algorithm matching complete partial matching table

Partial Match Table refers to the length of the longest common element of prefix and suffix.

For example, the prefix and suffix of the string "ABCDABD":

String Prefix Suffix Common Part Value ANaNNaNNaN 0ABNaN 0ABCA, ABC, BCNaN0ABCDA, AB, ABCD, CD, BCDNaN0ABCDAA, AB, ABC, ABCDA, CDA, BCDAA1ABCDABA, AB, ABC, ABCD, ABCDAB, AB, DAB, BCDABAB2ABCDABA, AB, ABC, ABCD, ABCDABD, BD, ABD, CDABD, BCDABDNaN0KMP Algorithm Implementation

Highlights:

Number of bits moved in KMP = number of matched characters-corresponding partial match value

import java.util.Arrays;public class KMPMatch { public static int Match(String str1, String str2, int[] next) { //initialize index int i = 0; int j = 0; for (; i

0 && str1.charAt(i) != str2.charAt(j)) { //Mismatch, back off i = i - next[j - 1]; j = 0; } //Match if (str1.charAt(i) == str2.charAt(j)) { j++; } //Return index if (j == str2.length()) { return i - j + 1; } } return -1; } //partial match public static int[] getNext(String s) { //define array int next[] = new int[s.length()]; //Initialize i, j int i = 0; int j = -1; next[0] = -1; //Traverse while (i < s.length() - 1) { if (j == -1 || s.charAt(i) == s.charAt(j)) { //Match successfully next[i] = j + 1; i++; j++; } else { //once the mismatch succeeds j falls back to-1 j = -1; } } return next; } public static void main(String[] args) { //String 1 String str1 = "BBCABCDAB ABCDABD"; //String 2 String str2 = "ABCDABD"; //matching table int[] next = getNext(str2); System.out.println(Arrays.toString(next)); // KMP algorithm int result = Match(str1, str2, next); System.out.println(result); }}

Output:

[0, 0, 0, 0, 1, 2, 0]

10

At this point, I believe that everyone has a deeper understanding of "how Java implements KMP algorithm," so let's actually operate it! Here is the website, more related content can enter the relevant channels for inquiry, pay attention to us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.