使用OC寫(xiě)算法之BF算法

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)始去匹配 例如:

image.png

很明顯我們下一次匹配的位置應(yīng)該是下圖這樣:

image.png

而不是從B開(kāi)始 雕薪,大牛們是無(wú)法忍受“暴力破解”這種低效的手段的昧诱,于是就有三個(gè)大牛一起研究出了我下篇文章要講的KMP算法,so所袁,下篇文章見(jiàn)盏档。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市燥爷,隨后出現(xiàn)的幾起案子蜈亩,更是在濱河造成了極大的恐慌懦窘,老刑警劉巖,帶你破解...
    沈念sama閱讀 212,657評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件稚配,死亡現(xiàn)場(chǎng)離奇詭異畅涂,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)道川,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,662評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門(mén)午衰,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人冒萄,你說(shuō)我怎么就攤上這事臊岸。” “怎么了尊流?”我有些...
    開(kāi)封第一講書(shū)人閱讀 158,143評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵帅戒,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我崖技,道長(zhǎng)逻住,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,732評(píng)論 1 284
  • 正文 為了忘掉前任迎献,我火速辦了婚禮鄙信,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘忿晕。我一直安慰自己装诡,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,837評(píng)論 6 386
  • 文/花漫 我一把揭開(kāi)白布践盼。 她就那樣靜靜地躺著鸦采,像睡著了一般。 火紅的嫁衣襯著肌膚如雪咕幻。 梳的紋絲不亂的頭發(fā)上渔伯,一...
    開(kāi)封第一講書(shū)人閱讀 50,036評(píng)論 1 291
  • 那天,我揣著相機(jī)與錄音肄程,去河邊找鬼锣吼。 笑死,一個(gè)胖子當(dāng)著我的面吹牛蓝厌,可吹牛的內(nèi)容都是我干的玄叠。 我是一名探鬼主播,決...
    沈念sama閱讀 39,126評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼拓提,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼读恃!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 37,868評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤寺惫,失蹤者是張志新(化名)和其女友劉穎疹吃,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體西雀,經(jīng)...
    沈念sama閱讀 44,315評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡萨驶,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,641評(píng)論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了艇肴。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片篡撵。...
    茶點(diǎn)故事閱讀 38,773評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖豆挽,靈堂內(nèi)的尸體忽然破棺而出育谬,到底是詐尸還是另有隱情,我是刑警寧澤帮哈,帶...
    沈念sama閱讀 34,470評(píng)論 4 333
  • 正文 年R本政府宣布膛檀,位于F島的核電站,受9級(jí)特大地震影響娘侍,放射性物質(zhì)發(fā)生泄漏咖刃。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,126評(píng)論 3 317
  • 文/蒙蒙 一憾筏、第九天 我趴在偏房一處隱蔽的房頂上張望嚎杨。 院中可真熱鬧,春花似錦氧腰、人聲如沸枫浙。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,859評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)箩帚。三九已至,卻和暖如春黄痪,著一層夾襖步出監(jiān)牢的瞬間紧帕,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,095評(píng)論 1 267
  • 我被黑心中介騙來(lái)泰國(guó)打工桅打, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留是嗜,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,584評(píng)論 2 362
  • 正文 我出身青樓挺尾,卻偏偏與公主長(zhǎng)得像鹅搪,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子潦嘶,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,676評(píng)論 2 351

推薦閱讀更多精彩內(nèi)容