Java实现字符串匹配算法KMP

kmp算法的核心思想：先对搜索字串生成偏移对照表，匹配时从左向右依次比较（bm从右向左，号称比kmp更快），相等则文档和搜索字串的下标+1迭代， 否则查表，定位最优的偏移位置（文档下标不变，搜索字串下标改变）。例外是，字符不匹配时，若搜索字串的下标为0，则文档的下标+1，继续迭代比较。

1. import?java.util.Arrays;??
2. ??
3. public?class?KMPSearch?{??
4. ????public?static?int[]?table;??
5. ????public?static?void?generateTab(String?key){//查询字串生成偏移对照表，一次迭代就可以??
6. ????????int?len=key.length();??
7. ????????table=new?int[len];??
8. ????????Arrays.fill(table,?0);??
9. ??????????
10. ????????for(int?i=1;i<len;i++){??
11. ????????????if(key.charAt(i)==key.charAt(table[i-1])){??
12. ????????????????table[i]=table[i-1]+1;??
13. ????????????}??
14. ????????}??
15. ????????for(int?v?:?table){??
16. ????????????System.out.print(v);??
17. ????????}??
18. ????????System.out.println();??
19. ????}??
20. ????public?static?int?KMPSearchs(String?doc,String?key){??
21. ????????generateTab(key);??
22. ????????int?result=-1;??
23. ????????int?doc_size=doc.length(),??
24. ????????????key_size=key.length(),??
25. ????????????doc_iter=,??
26. ????????????key_iter=;??
27. ????????while(doc_iter<doc_size){//遍历所查询的文档，同样，单层循环就可以实现→_→??
28. ????????????if(doc.charAt(doc_iter)==key.charAt(key_iter)){??
29. ????????????????doc_iter++;??
30. ????????????????key_iter++;??
31. ????????????}else{??
32. ????????????????if(key_iter==0){??
33. ????????????????????doc_iter++;??
34. ????????????????????continue;??
35. ????????????????}else{??
36. ????????????????????key_iter=table[key_iter-1];??
37. ????????????????????continue;??
38. ????????????????}??
39. ????????????}??
40. ????????????if(key_iter==key_size){??
41. ????????????????result=doc_iter-key_size;??
42. ????????????????break;??
43. ????????????}??
44. ????????}??
45. ????????return?result;??
46. ????}??
47. ????public?static?void?main(String[]?args){??
48. ????????int?i=KMPSearchs("bbc?abcdab?abcdabcdabde","abcdabd");??
49. ????????System.out.println(i);??
50. ????}??
51. }?
    

    import java.util.Arrays;  
      
    public class KMPSearch {  
        public static int[] table;  
        public static void generateTab(String key){//查询字串生成偏移对照表，一次迭代就可以  
            int len=key.length();  
            table=new int[len];  
            Arrays.fill(table,0);  
              
            for(int i=1;i<len;i++){  
                if(key.charAt(i)==key.charAt(table[i-1])){  
                    table[i]=table[i-1]+1;  
                }  
            }  
            for(int v : table){  
                System.out.print(v);  
            }  
            System.out.println();  
        }  
        public static int KMPSearchs(String doc,String key){  
            generateTab(key);  
            int result=-1;  
            int doc_size=doc.length(),key_size=key.length(),doc_iter=0,key_iter=0;  
            while(doc_iter<doc_size){//遍历所查询的文档，同样，单层循环就可以实现→_→  
                if(doc.charAt(doc_iter)==key.charAt(key_iter)){  
                    doc_iter++;  
                    key_iter++;  
                }else{  
                    if(key_iter==0){  
                        doc_iter++;  
                        continue;  
                    }else{  
                        key_iter=table[key_iter-1];  
                        continue;  
                    }  
                }  
                if(key_iter==key_size){  
                    result=doc_iter-key_size;  
                    break;  
                }  
            }  
            return result;  
        }  
        public static void main(String[] args){  
            int i=KMPSearchs("bbc abcdab abcdabcdabde","abcdabd");  
            System.out.println(i);  
        }  
    }