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

This article mainly introduces how to use java brute force matching and KMP algorithm to solve the string matching problem, the article is very detailed, has a certain reference value, interested friends must read it!

The problem to be solved?

1. Violent matching algorithm

A legend introduces the KMP algorithm String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD"

1. S [0] is Bline P [0] A, mismatch, execute ② instruction: "if there is a mismatch (i.e. S [I]! = P [j]), let I = I-(j-1), juni0", S [1] matches P [0], which means that the pattern string has to move one bit to the right.

2. S [1] and P [0] still do not match, continue to execute the ② instruction: "if there is a mismatch (that is, S [I]! = P [j]), let I = I-(j-1), jarg0", S [2] and P [0] match, so that the pattern string continues to move one bit to the right (keep executing "make I = I-(j-1), jarg0", I change from 2 to 4j has been 0)

3. Until S [4] and P [0] match successfully, following the idea of the above brute force matching algorithm, the ① instruction is executed instead: "if the current character matches successfully (i.e. S [I] = = P [j]), then S [I] is S [5] and P [j] is P [1], that is, S [5] matches P [1].

4. S [5] and P [1] match successfully, continue to execute the ① instruction: "if the current character match is successful (that is, S [I] = = P [j]), then the match between S [6] and P [2] is completed, and so on.

5. Until S [10] is a space character, and P [6] is a character D, because of a mismatch, re-execute the ② instruction: "if there is a mismatch (that is, S [I]! = P [j]), make I = I-(j-1), jroom0", which is equivalent to S [5] matching P [0].

6. So far, we can see that according to the idea of the violent matching algorithm, although the text string and pattern string have matched to S [9] and P [5] respectively, but because S [10] does not match P [6], so the text string goes back to S [5], and the pattern string goes back to P [0], so that S [5] matches P [0].

And S [5] must not match P [0]. Why? Because in the previous step 4 matching, we already know that S [5] = P [1] = B, and P [0] = A, that is, P [1]! = P [0], so S [5] must not be equal to P [0], so looking back will inevitably lead to mismatch. Is there an algorithm that allows I not to go back, but to move j?

The answer is yes. This algorithm is the KMP algorithm, which uses the valid information that has been partially matched before, keeps I from backtracking, and makes the pattern string move to a valid position as much as possible by changing the position of j.

Public class ViolenceMatch {public static void main (String [] args) {String str1 = "Silicon Valley, Silicon Valley, Silicon } / * brute force matching algorithm * / public static int violenceMatch (String str1, String str2) {char [] S1 = str1.toCharArray (); char [] S2 = str2.toCharArray (); int s1Len = s1.contains; int s2Len = s2.matching; int I = 0 / / I the index points to S1 int j = 0 position while / j index points to S2 index (I

< s1Len && j < s2Len) {// 保证匹配时，不越界 if (s1[i] == s2[j]) {// 匹配ok i++; j++; } else {// 没有匹配成功 // 如果不匹配(即str1[i] != str2[j],令i = i - (j - 1),j = 0) i = i - (j - 1); j = 0; } } // 判断是否匹配成功 if (j == s2Len) { return i - j; } else { return -1; } }} 暴力匹配算法的缺点：大量数据使用暴力匹配效率很低 二、KMP算法 关于KMP算法的学习，参考了这篇文章，此博主写的特别详细，大佬！ 很详尽KMP算法（厉害） - ZzUuOo666 - 博客园 算法介绍

The main idea of KMP is: 1. First get the partial matching table 2 of the substring. Use partial matching table to complete KMP matching

An illustration introduces the KMP algorithm

Code implementation public class KMPAlgorithm {public static void main (String [] args) {String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD"; int [] next= kmpNext ("ABCDABD"); System.out.println ("next=" + Arrays.toString (next)); int index = kmpSearch (str1, str2, next) System.out.println ("index=" + index) } / * kmp search algorithm * * @ param str1 original string * @ param str2 substring * @ param next partial matching table, which is the partial matching table corresponding to the substring * @ return. If-1, there is no match. Otherwise, return the first matching location * / public static int kmpSearch (String str1, String str2, int [] next) {/ / traversal for (int I = 0, j = 0) I

< str1.length(); i++) { // 需要处理 str1.charAt(i) != str2.charAt(j),去调整j的大小 // KMP算法核心点 while (j >

0 & & str1.charAt (I)! = str2.charAt (j)) {j = next [j-1];} if (str1.charAt (I) = = str2.charAt (j)) {jacks + } if (j = = str2.length ()) {/ / found return I-j + 1;}} return-1 } / * get the partial matching table of a string (substring) * / public static int [] kmpNext (String dest) {/ / create an next array to save partial matching values int [] next = new int [dest.length ()]; next [0] = 0 / / if the length of the string is 1, the matching value is 0 for (int I = 1, j = 0; I

< dest.length(); i++) { // 当dest.charAt(i) != dest.charAt(j)，需要从next[j - 1]获取新的j // 直到发现有dest.charAt(i) == dest.charAt(j)成立才退出 // 这是kmp算法核心点 while (j >

0 & & dest.charAt (I)! = dest.charAt (j)) {j = next [j-1];} if (dest.charAt (I) = = dest.charAt (j)) {jacks + } next [I] = j;} return next;}} these are all the contents of the article "how to use java brute force matching and KMP algorithm to solve string matching problems". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.