import java.util.Vector;
import java.util.Date;
class BreuteSearch{
static int[] lookup=new int[256];
//蛮力查找
public static Vector< Integer> brute0(String text,String str){
Vector< Integer> result =new Vector< Integer>();
for(int i=0;i< text.length();i++){
int flag=0;
for(int j=0;j< str.length();j++){
if(text.charAt(i+j)!=str.charAt(j)){
break;
}else{
flag++;
}
if(flag==str.length()){
result.add(i);
}
}
flag=0;
}
return result;
}
//蛮力查找优化版lookup查找表
public static Vector< Integer> brute1(String text,String str){
Vector< Integer> result=new Vector< Integer>();
lookup[str.charAt(0)]=2;
lookup[0]=1;
for(int i=0;i< text.length();i++){
switch(lookup[text.charAt(i)]){
case 0:break;
case 1:return null;
case 2:
int flag=0;
for(int j=1;j< str.length();j++){
if(text.charAt(i+j)!=str.charAt(j)){
break;
}else{
flag++;
}
if(flag==str.length()-1){
result.add(i);
}
}
default:break;
}
}
return result;
}
public static void main(String[] argv){
String text="sunzongbaoonhahahahahsunzongbaoons.....";//假设从文本中读出很长一段
String str="ong";
long time00=new Date().getTime();
Vector result0=brute0(text,str);
long time01=new Date().getTime();
long time10=new Date().getTime();
Vector result1=brute1(text,str);
long time11=new Date().getTime();
System.out.println("Time1:"+(time01-time00));
System.out.println("Time2:"+(time11-time10));//明显第二种的效率高了很多
}
}
虽然优化版本的能力比较好,但是遇见如aaaaaaaaaaaaaaaaaaa...ab中查找ac的话依然会陷入普通蛮力查找的漩涡,显然这种情况是最坏情况。
最坏 O(str.len*text.len);
典型 O(text.length);
准备时间 无 |