Go语言视频零基础入门到精通

javalearner

背景简介：KMP算法用来处理字符串匹配的。给你A,B两个字符串，检查B串是否是A串的子串，类似于java的String.indexOf("")。之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。      原理介绍：找到匹配失败时的最合适的回退位置，而不是简单的回退到子串的第一个字符（常规的枚举查找方式，是简单的回退到子串的第一个字符，接下来准备写一篇KMP算法的性能分析Java实现实例），即可提高查找的效率。因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组。过多的理论就不介绍了。 总体而言比较简单，KMP算一个经典的算法例子，很多笔试、面试也会问起。现总结一下，放在这里供大家参考、交流，希望对大家有所帮助，下面直接给出实现例子，测试与分析也包含其中。 一、一个文件源代码
  
   
   
     
   

     
   
  
KMP.java 源代码为：
package algorithm.kmp;

1. /**
   
2. * KMP算法的Java实现例子与测试、分析
   
3. * @author 崔卫兵
   
4. * @date 2009-3-25
   
5. */
   
6. public class KMP {
   
7. /**
   
8.   * 对子串加以预处理，从而找到匹配失败时子串回退的位置
   
9.   * 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
   
10.   * 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
    
11.   * @param B，待查找子串的char数组
    
12.   * @return
    
13.   */
    
14. public static int[] preProcess(char [] B) {
    
15.   int size = B.length;
    
16.   int[] P = new int[size];
    
17.   P[0]=0;
    
18.   int j=0;
    
19.   //每循环一次，就会找到一个回退位置
    
20.   for(int i=1;i< size;i++){
    
21.    //当找到第一个匹配的字符时，即j>0时才会执行这个循环
    
22.    //或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
    
23.    //p1
    
24.    while(j>0 && B[j]!=B[i]){
    
25.     j=P[j];
    
26.    }
    
27.    //p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
    
28.    if(B[j]==B[i]){
    
29.     j++;
    
30.    }
    
31.    //找到一个回退位置j，把其放入P[i]中
    
32.    P[i]=j;
    
33.   }
    
34.   return P;
    
35. }
    
36. /**
    
37.   * KMP实现
    
38.   * @param parStr
    
39.   * @param subStr
    
40.   * @return
    
41.   */
    
42. public static void kmp(String parStr, String subStr) {
    
43.   int subSize = subStr.length();
    
44.   int parSize = parStr.length();
    
45.   char[] B = subStr.toCharArray();
    
46.   char[] A = parStr.toCharArray();
    
47.   int[] P = preProcess(B);
    
48.   int j=0;
    
49.   int k =0;
    
50.   for(int i=0;i< parSize;i++){
    
51.    //当找到第一个匹配的字符时，即j>0时才会执行这个循环
    
52.    //或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
    
53.    //p1
    
54.    while(j>0 && B[j]!=A[i]){
    
55.     //找到合适的回退位置
    
56.     j=P[j-1];
    
57.    }
    
58.    //p2 找到一个匹配的字符
    
59.    if(B[j]==A[i]){
    
60.     j++;
    
61.    }
    
62.    //输出匹配结果，并且让比较继续下去
    
63.    if(j==subSize){
    
64.     j=P[j-1];
    
65.     k++;
    
66.     System.out.printf("Find subString "%s" at %d
67. ",subStr,i-subSize+1);
    
68.    }
    
69.   }
    
70.   System.out.printf("Totally found %d times for "%s".
72. ",k,subStr);
    
73. }
    
74. public static void main(String[] args) {
    
75.   //回退位置数组为P[0, 0, 0, 0, 0, 0]
    
76.   kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
    
77.   //回退位置数组为P[0, 0, 1, 2, 3, 4]
    
78.   kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");
    
79.   //回退位置数组为P[0, 0, 0]
    
80.   kmp("测试汉字的匹配，崔卫兵。这个会匹配1次","崔卫兵");
    
81.   //回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
    
82.   kmp("这个会匹配0次","it1it1it1");
    
83. }
    
84. }

复制代码

二、输出结果 Find subString "abcdef" at 16 Totally found 1 times for "abcdef". Find subString "ititit" at 11 Find subString "ititit" at 24 Totally found 2 times for "ititit". Find subString "崔卫兵" at 8 Totally found 1 times for "崔卫兵". Totally found 0 times for "it1it1it1". 三、总结 总体而言，KMP算法通过找到合适的回退位置从而可以提高匹配效率，但是如果匹配位置都是第一个字符呢？例如测试代码中的 //回退位置数组为P[0, 0, 0, 0, 0, 0] kmp("abcdeg, abcdeh, abcdef!这个会匹配2次","abcdef"); 接下来准备写一篇KMP算法的性能分析Java实现实例，下文再见。^_^


  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/11/000320359.zip