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

javalearner

1. import java.io.*;
   
2. /** * @author iChuan * */
   
3. public class KMP {
   
4. private static String a;
   
5. private static String b;
   
6. private static int[] p;  
   
7. /**  * 从标准输入读取a串和b串
   
8.   * @param args
   
9.   * @throws IOException
   
10.   */
    
11.    public static void main(String args[]) throws IOException{
    
12.     System.out.println("Input the content string:");
    
13.      BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
    
14.      a = stdin.readLine();  //a="abcabcabcabcdabcxabcabc"
    
15.      System.out.println("And the string you want to search:");
    
16.      b = stdin.readLine();
    
17.      //b="abcabc";
    
18.      KMP.Next();
    
19.      for(int i=0;i< b.length();i++)
    
20.          System.out.print(b.charAt(i)+"  ");
    
21.      System.out.println();
    
22.      for(int i=0;i< p.length;i++)
    
23.          System.out.print(p[i]+"  ");
    
24.      System.out.println();
    
25.      KMP.match();
    
26.    }
    
27.    public  static void Next() {//建立模式串P的next[]表
    
28.     p = new int[b.length()];
    
29.     int j = 0;//“主”串指针
    
30.     int t = p[0] = -1;//“模式”串指针
    
31.     while (j < b.length()-1)
    
32.         if (0 > t || b.charAt(j) == b.charAt(t)) {//匹配
    
33.            j++; t++;
    
34.            p[j] = t;
    
35.         } else//失配
    
36.            t =p[t];
    
37.     }
    
38.      /**
    
39.       * 开始在a串中寻找b串的匹配，每找到一个就打印出对应a中的索引
    
40.       */
    
41.      public static void match(){
    
42.        int j = -1;
    
43.        for (int i = 0; i < a.length(); i++){
    
44.         while (j > 0 && (b.charAt(j + 1) != a.charAt(i)))
    
45.          j = p[j];
    
46.         if (b.charAt(j + 1) == a.charAt(i))  
    
47.          j++;
    
48.         if (j + 1 == b.length()){
    
49.          System.out.println("matched at " + String.valueOf(i + 1 - b.length()));
    
50.          j = -1;
    
51.          i=i-b.length()+2;
    
52.         }
    
53.       }
    
54.       System.out.println("All done!");
    
55.     }
    
56. }

复制代码

运行:
C:work>java KMP
Input the content string:
abcabcabcabcdabcxabcabc
And the string you want to search:
abcabc
a b c a b c
-1 0 0 0 1 2
matched at 0
matched at 3
matched at 6
matched at 17
All done!

  


源码下载：http://file.javaxxz.com/2014/12/1/000555156.zip