kmp算法的核心思想：先對(duì)搜索字串生成偏移對(duì)照表，匹配時(shí)從左向右依次比較（bm從右向左，號(hào)稱比kmp更快），相等則文檔和搜索字串的下標(biāo)+1迭代， 否則查表，定位最優(yōu)的偏移位置（文檔下標(biāo)不變，搜索字串下標(biāo)改變）。例外是，字符不匹配時(shí)，若搜索字串的下標(biāo)為0，則文檔的下標(biāo)+1，繼續(xù)迭代比較。

1. import java.util.Arrays;  
2.   
3. public class KMPSearch {  
4.     public static int[] table;  
5.     public static void generateTab(String key){//查詢字串生成偏移對(duì)照表，一次迭代就可以  
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){//遍歷所查詢的文檔，同樣，單層循環(huán)就可以實(shí)現(xiàn)→_→  
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){//查詢字串生成偏移對(duì)照表，一次迭代就可以  
            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){//遍歷所查詢的文檔，同樣，單層循環(huán)就可以實(shí)現(xiàn)→_→  
                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);  
        }  
    }  

標(biāo)簽： 搜索

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。