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

javalearner

1. import java.util.Vector;   
   
2. import java.util.Date;   
   
3. class BreuteSearch{   
   
4. static int[] lookup=new int[256];   
   
5.   
   
6. //蛮力查找   
   
7. public static Vector< Integer> brute0(String text,String str){   
   
8.      
   
9.   Vector< Integer> result =new Vector< Integer>();   
   
10.   for(int i=0;i< text.length();i++){   
    
11.     int flag=0;   
    
12.     for(int j=0;j< str.length();j++){   
    
13.         
    
14.      if(text.charAt(i+j)!=str.charAt(j)){   
    
15.       break;   
    
16.      }else{   
    
17.       flag++;   
    
18.      }   
    
19.   
    
20.      if(flag==str.length()){   
    
21.       result.add(i);   
    
22.          
    
23.      }   
    
24.       
    
25.     }   
    
26.   
    
27.     flag=0;     
    
28.   
    
29.   }   
    
30.   
    
31.   return result;     
    
32.   
    
33. }   
    
34.   
    
35.    
    
36.   
    
37. //蛮力查找优化版lookup查找表   
    
38. public static Vector< Integer> brute1(String text,String str){   
    
39.      
    
40.   Vector< Integer> result=new Vector< Integer>();   
    
41.   
    
42.   lookup[str.charAt(0)]=2;   
    
43.   lookup[0]=1;   
    
44.      
    
45.   for(int i=0;i< text.length();i++){   
    
46.    switch(lookup[text.charAt(i)]){   
    
47.     case 0:break;   
    
48.     case 1:return null;   
    
49.     case 2:   
    
50.      int flag=0;   
    
51.      for(int j=1;j< str.length();j++){   
    
52.       if(text.charAt(i+j)!=str.charAt(j)){   
    
53.        break;   
    
54.       }else{   
    
55.        flag++;   
    
56.       }   
    
57.          
    
58.       if(flag==str.length()-1){   
    
59.        result.add(i);   
    
60.       }   
    
61.      }   
    
62.     default:break;   
    
63.    }   
    
64.   }   
    
65.   
    
66.   return result;   
    
67.   
    
68. }   
    
69.    
    
70. public static void main(String[] argv){   
    
71.   
    
72.    String  text="sunzongbaoonhahahahahsunzongbaoons.....";//假设从文本中读出很长一段   
    
73.       
    
74.    String str="ong";   
    
75.    long time00=new Date().getTime();   
    
76.    Vector
77.    
78.       result0=brute0(text,str);   
    
79.    long time01=new Date().getTime();   
    
80.   
    
81.    long time10=new Date().getTime();   
    
82.    Vector
83.      
84.        result1=brute1(text,str);   
    
85.    long time11=new Date().getTime();   
    
86.   
    
87.     System.out.println("Time1:"+(time01-time00));   
    
88.     System.out.println("Time2:"+(time11-time10));//明显第二种的效率高了很多   
    
89.       
    
90. }   
    
91.   
    
92.   
    
93. }   
    
94.   
    
96.      
97.    

复制代码

虽然优化版本的能力比较好，但是遇见如aaaaaaaaaaaaaaaaaaa...ab中查找ac的话依然会陷入普通蛮力查找的漩涡，显然这种情况是最坏情况。


最坏 O(str.len*text.len);

典型 O(text.length);

准备时间 无


   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/23/000610234.zip