1.0 问题描述

实现KMP算法查找字符串。

2.0 问题分析

“KMP算法”是对字符串查找“简单算法”的优化。

字符串查找“简单算法”是源字符串每个字符分别使用匹配串进行匹配，一旦失配，模式串下标归0，源字符串下标加1。

可以很容易计算字符串查找“简单算法”的时间复杂度为O（m*n），其中n表示源字符串长度，m表示匹配串长度。

KMP算法的匹配方式同简单算法的匹配方式相同，只不过在失配的时候，模式串下标不归零，反而会根据模式串自身的重复信息，回归到一个大于0的下标。从而减少匹配次数。

那么失配时候，模式串下标回归的位置需要提前计算好。计算的方法是，匹配串中，每个位置的前缀字符串“头部”和“尾部”的重复字符数即为失配下标回归位置。
- 假设匹配串是：ababc
- 下标0的字符是“a”，它的前缀是空字符串，所以回归位置为0
- 下标1的字符是“b”，它的前缀是“a”，数量不足2个，回归位置也是0
- 下标2的字符是“a”，他的前缀是“ab”，没有重复的头部和尾部，回归位置是0
- 下标3的字符是“b”，它的前缀是“aba”，有重复的头部和尾部，重复子串是“a”，长度为1，回归位置是1
- 下标3的字符是“c”，它的前缀是“abab”，有重复的头部和尾部，重复子串是“ab”，长度为2，回归位置是2

根据上一条，我们可以计算出一个next数组用于保存失配时模式串下标应该回到哪里的下标序列。

计算好next数组后，就可以使用“简单算法”的逻辑进行匹配了，只不过不同的是，一旦失配，匹配串下标不是回归到0，而是根据next数组决定。

3.0 代码实现

3.1使用swift实现

///简单查找func simpleSearch(_ src: String, _ mode: String, _ start: Int) -> Int {    var i = start;    while i < src.count {        var j = 0;        while j < mode.count {            if(i + j >= src.count || src[i + j] != mode[j]){                break;            }            j += 1;        }        if j == mode.count{            return i;        }        i += 1;    }    return -1;}///kmp字符串查找func kmpSearch(_ src: String, _ mode: String, _ start: Int) -> Int {    //计算next    var next: [Int] = [0, 0];    //自身匹配，i表示主下标，j表示匹配下标    var i = 2, j = 0;    while i < mode.count {        if(mode[i - 1] == mode[j]){            next[i] = j + 1;            i += 1;            j += 1;        }else{            if(j == 0){                i += 1;            }            //已经匹配的部分有可能会有首尾相同的情况            j = next[j];        }    }        //算法同自身匹配    i = start;    j = 0;    while i < src.count {        if(src[i] == mode[j]){            i += 1;            j += 1;                        if(j == mode.count){                return i - mode.count;            }        }else{            if(j == 0){                i += 1;            }            j = next[j];        }    }        return -1;}复制代码

3.2使用js实现

function simpleSearch(src, mode, start){    for(let i = start; i < src.length; i++){        let miss = false;        for(let j = 0; j < mode.length; j++){            if(i + j >= src.length){                miss = true;                break;            }else if(src.charAt(i + j) != mode.charAt(j)){                miss = true;                break;            }        }        if(!miss){            return i;        }    }    return -1;}function kmpSearch(src, mode, start){    let next = [0, 0];    let i = 2;     let j = 0;    while (i < mode.length) {        if(mode.charAt(i - 1) == mode.charAt(j)){            j++;            i++;            next[i-1] = j;        }else{            if(j == 0){                i++;            }            j = next[j];        }    }    i = start;    j = 0;    let found = false;    while (i <= src.length) {        if(src.charAt(i) == mode.charAt(j)){            i++;            j++;            if(j == mode.length){                found = true;                break;            }        }else{            if(j == 0){                i++;            }            j = next[j];        }    }    if(found){        return i - mode.length;    }else{        return -1;    }}复制代码

4.0 复杂度分析

我们选取复杂度最大的一种模型来分析，即：模式串所有字符都相同，源串和模式串总是在最后一位失配。

令源串为 “aaaabaaaabaaaab”，匹配串为 “aaaaa”。

匹配串的next数组为：[0,0,1,2,3]

首次匹配会在第5位失配，比较次数为5。

模式串回到3，进行一次比较即会失配，比较次数为1。

模式串回到1，进行一次比较即会失配，比较次数为1。

模式串回到0，同时源串下标加1。此时源串下标为6，匹配串下标为0。根据源串特点，此时会不断重复4-7的过程。

根据上述分析，我们推到一般情况，长度为n的源串，长度为m的匹配串，会形成一个周期性匹配，周期次数为n/m。

很容易看到一个周期内的复杂度小于O(2m)，所以整体复杂度小于 O(2m*n/m)=O(2n)，即复杂度为O(n)。

计算next数组的算法和匹配算法相同，因此复杂度为O(m)。

所以KMP算法整体复杂度为O(m+n)。