BF（Brute Force）算法核心思想是：首先S[1]和T[1]比較，若相等，則再比較S[2]和T[2]，一直到T[M]為止；若S[1]和T[1]不等，則T向 右移動一個字符的位置，再依次進行比較。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，則匹配成功；否則失敗。該算法最壞情況下要進行 M*(N-M+1)次比較，
時間復雜度為O(M*N)
比如: String a ="123456789" String b= "23"
其實就是循環 a一個一個字符匹配，開始a[0]和b[0]匹配，沒有找到，直接不用找b[1]，直接用a[1]和b[0]匹配發現已經 找到，然后繼續用
a[2]和b[1]匹配發現已經 找到。前且是b字符串末尾。說明已經完全找到。返回結果
JAVA代碼實現
/**
* 匹配字符串，判斷 b字符串在a出現的起始位置，沒有找到返回（-1）
* @param a
* @param b
* @return
*/
public static int indexOf(String a,String b){
char[] as = a.toCharArray();
char[] bs = b.toCharArray();
int begin = 0;
for(int i = 0 ; i <as.length; i++){
int k = nextStr(as[i], bs,begin);
//說明已經找到
if( k == begin ){
return i-begin;
}
//說明找到一個字符，需要繼續找
else if( k >= 0 ){
begin = k;
}else{
//沒有找到繼續找
begin = 0;
}
}
return -1;
}
/**
* 匹配字符串，找到字符串位置
* @param c
* @param cs
* @param begin
* @return
*/
public static int nextStr(char c,char[] cs,int begin){
//如果字符匹配和已經到了字符尾部青示已經全部匹配
if(cs[begin] == c && begin == (cs.length-1) ){
return begin;
//如果字符匹配但沒有到尾部需要繼續下移
}else if(cs[begin] == c){
return begin+1;
}
//完全沒有匹配
else{
return -1;
}
}
然后在main里面調用indexOf方法看到結果
posted on 2013-05-21 16:11
青菜貓(孫宇) 閱讀(1016)
評論(0) 編輯 收藏 所屬分類:
其它