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

五菱

import java.io.*;
/** * @author iChuan * */
public class KMP {
private static String a;
private static String b;
private static int[] p;  
/**  * 从标准输入读取a串和b串
  * @param args
  * @throws IOException
  */
   public static void main(String args[]) throws IOException{
    System.out.println("Input the content string:");
     BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
     a = stdin.readLine();  //a="abcabcabcabcdabcxabcabc"
     System.out.println("And the string you want to search:");
     b = stdin.readLine();
     //b="abcabc";
     KMP.Next();
     for(int i=0;i< b.length();i++)
         System.out.print(b.charAt(i)+"  ");
     System.out.println();
     for(int i=0;i< p.length;i++)
         System.out.print(p+"  ");
     System.out.println();
     KMP.match();
   }
   public  static void Next() {//建立模式串P的next[]表
    p = new int[b.length()];
    int j = 0;//“主”串指针
    int t = p[0] = -1;//“模式”串指针
    while (j < b.length()-1)
    if (0 > t || b.charAt(j) == b.charAt(t)) {//匹配
       j++; t++;
       p[j] = t;
    } else//失配
       t =p[t];
    }
     /**
      * 开始在a串中寻找b串的匹配，每找到一个就打印出对应a中的索引
      */
     public static void match(){
       int j = -1;
       for (int i = 0; i < a.length(); i++){
        while (j > 0 && (b.charAt(j + 1) != a.charAt(i)))
         j = p[j];
        if (b.charAt(j + 1) == a.charAt(i))  
         j++;
        if (j + 1 == b.length()){
         System.out.println("matched at " + String.valueOf(i + 1 - b.length()));
         j = -1;
         i=i-b.length()+2;
        }
      }
      System.out.println("All done!");
    }
}
运行:
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!