KMP算法

 1 import java.util.*;
 2 
 3 public class KMP {
 4     public static void main(String args[]){
 5         System.out.println("输入字符串：");        
 6         Scanner scan = new Scanner(System.in);
 7         String inStr= scan.nextLine();
 8         scan = new Scanner(System.in);
 9         System.out.println("输入匹配字符串：");    
10         String match= scan.nextLine();
11         System.out.println(KMP(inStr,match));
12     //    System.out.println(KMP("BCC ABCDAB ABCDABCDABDE","ABCDABD"));
13     }
14     public static int KMP(String inStr,String match){
15         //1.求next数组
16         int next[]=new int[match.length()+1];
17         int i=0;//next下标
18         int j=-1;//next的值。表示在当前下标i之前，最长相同真前缀的长度是j。i=1时默认是-1，之后递增。
19         next[0]=-1;
20         while(i<match.length()){
21             if(j==-1 || match.charAt(i)==match.charAt(j)  ){//如果i=0 或 前缀能匹配的上
22                 i++;
23                 j++;
24                 next[i]=j;
25             }else{
26                 j=next[j];//next[j]代表 [0, j - 1] 区段中最长相同真前后缀的长度。
27             }
28         }/*
29         for(i=0;i<match.length()+1;i++)
30             System.out.print(next[i]+",");*/
31         i=0;
32         j=0;
33         while(i<inStr.length() && j<match.length()){
34             if(j==-1 || inStr.charAt(i)==match.charAt(j) ){//第一个字符不匹配 或者匹配成功
35                 i++;
36                 j++;//如果是-1（第一个字符不匹配），通过这个语句就置1了。
37             }
38             else{
39                 j=next[j];
40             }
41         }
42         if(j==match.length()) //之所以是match.length 不是 length-1 是因为判断成功后先行进行了i++和j++的操作。
43             return i-j;   //此时i移动到了j的末端。所以是i-j
44         return -1;
45     }
46 }