序言

當(dāng)簡(jiǎn)友們看到這篇文章的時(shí)候，我默認(rèn)大家都已經(jīng)了解過(guò)BF算法了，如果有對(duì)BF算法不了解的，建議可以先看下我上一篇文章：傳送門

KMP簡(jiǎn)介

KMP簡(jiǎn)單來(lái)說(shuō)是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt共同發(fā)現(xiàn)的，看到這三位大牛的名字，我想你應(yīng)該明白為什么叫KMP算法了，KMP算法要解決的問(wèn)題就是在字符串（也叫主串）中的模式（pattern）定位問(wèn)題。說(shuō)簡(jiǎn)單點(diǎn)就是我們平時(shí)常說(shuō)的關(guān)鍵字搜索。模式串就是關(guān)鍵字（接下來(lái)稱它為P），如果它在一個(gè)主串（接下來(lái)稱為T）中出現(xiàn)，就返回它的具體位置，否則返回-1（常用手段）。

BF算法存在的問(wèn)題以及KMP解決的問(wèn)題

其實(shí)BF算法存在的問(wèn)題和KMP要解決的問(wèn)題本身是一個(gè)問(wèn)題，因?yàn)镵MP要解決的問(wèn)題恰好就是BF算法所存在的問(wèn)題，在上篇文章其實(shí)我就有介紹BF算法存在的問(wèn)題，這里我還是再簡(jiǎn)單介紹一下吧：
首先我們先看下BF算法的實(shí)現(xiàn)代碼：

 @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從頭開始
            i = i - j + 1;
            j = 0;
        }
    }
    
    //到這一步 判斷如果j == 字符串長(zhǎng)度證明匹配成功
    if (j == target.length ) {
        return i - j;
    }
    return -1;
}

了解BF算法的人應(yīng)該都知道有一個(gè)痛點(diǎn)，因?yàn)樗臅r(shí)間復(fù)雜度是M*N的，每一次匹配之后，當(dāng)遇到匹配不成功的時(shí)候，又要重頭開始去匹配，這是沒(méi)有必要的，例如下面的例子：

image.png

很明顯我們可以看到在這里C 和 D 無(wú)法匹配了，這時(shí)候如果按照BF算法的解法，我們理所當(dāng)然就應(yīng)該是拿A和B去匹配，這里很明顯是沒(méi)必要的，我們可以直接像下圖一樣匹配：

image.png

這里我就不用給大家證明為啥了吧,看不出來(lái)的一個(gè)一個(gè)試一下就清楚了，看到這里，我想大家應(yīng)該知道KMP是為了解決一個(gè)什么問(wèn)題了。

next數(shù)組的求法

大家都稱這個(gè)存放j下一個(gè)匹配位置的數(shù)組叫做next，那我這里也就叫它next數(shù)組吧，從字面上來(lái)看 我們也知道，這個(gè)next數(shù)組其實(shí)就是存放下一個(gè)要匹配的位置，也就是要移動(dòng)的位數(shù)，下面我們不廢話直接上代碼(有詳細(xì)的注釋 不要為難我去解釋到底next數(shù)組到底怎么生成了好不好？)：

/**
 獲取next數(shù)組

 @param pString 匹配字符串
 @return next數(shù)組
 */
- (NSArray *)getNextArray:(NSString *)pString {
    NSMutableArray *nextA = [NSMutableArray arrayWithCapacity:pString.length];
    //定義前綴索引
    int j = -1;
    //定義后綴索引 大于前綴索引
    int i = 0;
    //給next數(shù)組的第0個(gè)元素賦值為-1
    nextA[0] = @(-1);
    while (i < pString.length) {
        if (-1 == j || [pString characterAtIndex:i] == [pString characterAtIndex:j]) {
            //當(dāng)前綴和后綴相等時(shí)
            i++;
            j++;
            //給next數(shù)組的元素賦值
            nextA[i] = @(j);//這里說(shuō)明一下 假設(shè)pString是 @"aba"  第0個(gè)元素的a 和 第2個(gè)元素的a相等 那么next[2]就應(yīng)該是1 也就是要往后挪動(dòng)一個(gè)位置
        }else {
            //當(dāng)兩個(gè)字符不相等的時(shí)候 我們就需要回溯 那具體回溯的位置是哪里呢？ 一句next數(shù)組的概念 它里面存放的元素是下一次要移動(dòng)的位數(shù) 所以我們的j = nextA[j]
            j = [nextA[j] intValue];
        }
        
    }
    
    return nextA;
}

KMP算法實(shí)現(xiàn)

#pragma  mark -  KMP算法
#pragma  mark -

/**
 KMP算法

 @param tString 主串
 @param pString 字串
 @return 匹配成功返回匹配成功位置 失敗返回-1
 */
- (int)KMP:(NSString *)tString pString:(NSString *)pString {
    //主串tString的索引
    int i = 0;
    //字串pString的索引
    int j = 0;
    //獲取主串和字串的字符串長(zhǎng)度（特別注意因?yàn)槭褂胠ength獲取的長(zhǎng)度是NSUInteger類型的,直接和它對(duì)比會(huì)出現(xiàn)問(wèn)題 所以這里我都強(qiáng)制轉(zhuǎn)換為int）
    int tLength = (int)tString.length;
    int pLength = (int)pString.length;
    //獲取next數(shù)組
    NSArray *nextArray = [self getNextArray:pString];
    while (i < tLength && j < pLength) {
        if (-1 == j || [tString characterAtIndex:i] == [pString characterAtIndex:j]) {
            i++;
            j++;
        }else {
            //回溯到下一個(gè)位置
            j = [nextArray[j] intValue];
        }
    }
    if (j == pLength) {
        return i- j;
    }
    
    return -1;
}

我們可以看到這個(gè)和BF算法唯一不同的地方就是，在匹配失效的時(shí)候 j的索引位置不在是：

  i = i - j + 1;
  j = 0;

而是換成了從next數(shù)組來(lái)獲?。?/p>

 //回溯到下一個(gè)位置
 j = [nextArray[j] intValue];

這樣就把KMP算法的核心問(wèn)題換成了怎么獲取next數(shù)組，所以大家多多理解next數(shù)組的代碼吧。有什么地方?jīng)]有理解的可以留言。