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

吴会

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);

准备时间 无