BF算法簡(jiǎn)介
BF算法是Brute Force算法的簡(jiǎn)稱(chēng)(如果你發(fā)揮你得想象 你也可以稱(chēng)之為Boy Friend算法)昭卓,BF算法的思想就是將目標(biāo)串S的第一個(gè)字符與模式串T的第一個(gè)字符進(jìn)行匹配,若相等游盲,則繼續(xù)比較S的第二個(gè)字符和 T的第二個(gè)字符;若不相等荧恍,則比較S的第二個(gè)字符和T的第一個(gè)字符和屎,依次比較下去,直到得出最后的匹配結(jié)果庸汗。正是因?yàn)檫@種蠻干的比較,也被稱(chēng)為蠻干算法
BF算法代碼實(shí)現(xiàn)方式1
#pragma mark - 暴力的BF算法
#pragma mark -
/**
傳入一個(gè)主串和字串 匹配是否能匹配成功
@param source 主串
@param target 字串
@return 成功返回主串中開(kāi)始索引 失敗返回-1
*/
- (int)bruteForce1WithSource:(NSString *)source target:(NSString *)target {
//主串遍歷
for (int i = 0; i < source.length; i++) {
//目標(biāo)字符串遍歷
for (int j = 0; j < target.length; j++) {
//關(guān)鍵在于這句 從主串中取值 當(dāng)i確定時(shí) 需要加上j來(lái)往后挪動(dòng)位置 不相等就直接break
if ([source characterAtIndex:i + j] != [target characterAtIndex:j]) {
break;
}
//當(dāng)索引到了字符串最后一個(gè)字符時(shí)就證明匹配成功
if (j == target.length -1) {
return i;
}
}
}
return -1;
}
BF算法代碼實(shí)現(xiàn)方式2
一般來(lái)說(shuō)我們都用這種方式來(lái)實(shí)現(xiàn)逻锐,因?yàn)樯厦孢@種有些人可能不是很能接受
/**
暴力匹配字符解法2
@param source 原字符串
@param target 匹配字符串
@return 成功返回索引 失敗返回-1
*/
- (int)bruteForce2WithSource:(NSString *)source target:(NSString *)target {
//主串索引
int i = 0;
//字串索引
int j = 0;
while (i < source.length && j < target.length) {
//依次來(lái)一個(gè)一個(gè)對(duì)比
if ([source characterAtIndex:i] == [target characterAtIndex:j]) {
i++;
j++;
}else {//索引回溯 i的索引變化為下一個(gè)也就是 (i- j +1)而j = 0從頭開(kāi)始
i = i - j + 1;
j = 0;
}
}
//到這一步 判斷如果j == 字符串長(zhǎng)度證明匹配成功
if (j == target.length ) {
return i - j;
}
return -1;
}
BF存在的問(wèn)題和下篇預(yù)告
很明顯我們可以看到BF算法是存在很大缺陷的夫晌,因?yàn)橛行┣闆r我們根本不需要從頭來(lái)開(kāi)始去匹配 例如:
很明顯我們下一次匹配的位置應(yīng)該是下圖這樣:
而不是從B開(kāi)始 雕薪,大牛們是無(wú)法忍受“暴力破解”這種低效的手段的昧诱,于是就有三個(gè)大牛一起研究出了我下篇文章要講的KMP算法,so所袁,下篇文章見(jiàn)盏档。