算法(2)KMP算法

279 阅读4分钟

1.0 问题描述

实现KMP算法查找字符串。

2.0 问题分析

  1. “KMP算法”是对字符串查找“简单算法”的优化。
  2. 字符串查找“简单算法”是源字符串每个字符分别使用匹配串进行匹配,一旦失配,模式串下标归0,源字符串下标加1。
  3. 可以很容易计算字符串查找“简单算法”的时间复杂度为O(m*n),其中n表示源字符串长度,m表示匹配串长度。
  4. KMP算法的匹配方式同简单算法的匹配方式相同,只不过在失配的时候,模式串下标不归零,反而会根据模式串自身的重复信息,回归到一个大于0的下标。从而减少匹配次数。
  5. 那么失配时候,模式串下标回归的位置需要提前计算好。计算的方法是,匹配串中,每个位置的前缀字符串“头部”和“尾部”的重复字符数即为失配下标回归位置。
    • 假设匹配串是: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
  6. 根据上一条,我们可以计算出一个next数组用于保存失配时模式串下标应该回到哪里的下标序列。
  7. 计算好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 复杂度分析

  1. 我们选取复杂度最大的一种模型来分析,即:模式串所有字符都相同,源串和模式串总是在最后一位失配。
  2. 令源串为 “aaaabaaaabaaaab”,匹配串为 “aaaaa”。
  3. 匹配串的next数组为:[0,0,1,2,3]
  4. 首次匹配会在第5位失配,比较次数为5。
  5. 模式串回到3,进行一次比较即会失配,比较次数为1。
  6. 模式串回到1,进行一次比较即会失配,比较次数为1。
  7. 模式串回到0,同时源串下标加1。此时源串下标为6,匹配串下标为0。根据源串特点,此时会不断重复4-7的过程。
  8. 根据上述分析,我们推到一般情况,长度为n的源串,长度为m的匹配串,会形成一个周期性匹配,周期次数为n/m。
  9. 很容易看到一个周期内的复杂度小于O(2m),所以整体复杂度小于 O(2m*n/m)=O(2n),即复杂度为O(n)。
  10. 计算next数组的算法和匹配算法相同,因此复杂度为O(m)。
  11. 所以KMP算法整体复杂度为O(m+n)。