数据结构与算法(九) -- KMP匹配算法

248 阅读11分钟

一、简介

KMP算法是由 D.E.Knuth、J.H.Morris、和V.R.Pratt共同发表的模式匹配算法, 称之为克鲁特-莫里斯-普特拉算法. 简称为KMP算法

二、KMP原理探索

(下文中所有字符串均从1下标记开始, 0下标用来记录字符串长度) 假设, 主串S = "abcdefgabcdex", 模式串为 T = "abcdex". i为主串当前位置, j为模式串当前位置.

当我们使用BF算法进行匹配的时候, 会依次主串与模式串对比.

这个过程第二次中, T[1]与T[2]不等, S[2]与T[2]相等. 所以T[1]必定不等于S[2], 但是BF算法还是进行了一次比较, 这个比较就是多余的.

在T串中, 字符之间都是不同都, 那么也就意味着, 当我们进行字符匹配当时候, 哪个位置匹配不上, 我们只需要将模式串回溯到头部, 主串位置不变, 进行重新匹配.

这样就省去了T[1]与 S[2] S[3] S[4] S[5] 匹配的步骤.

三、KMP的next数组值计算

在上文的当模式串中没有重复的字符时, 匹配错误的时候, 会将模式串位置回溯到头部.

但是如果模式串中有重复的字符的话, 这个模式串回溯到头部将会出现问题.

所以KMP中用一个next数组来记录一下当某一个位置匹配失败的时候, 模式串应该回溯到哪一个位置.

T模式串中各个位置j值变化, 也就是匹配错误的时候, 需要回溯的位置用next表示, 那么next的长度就是模式串T的长度, 于是可以得出下面函数的定义:

3.1、非重复字符的模式串

首先来看一下模式串中不存在重复的情况

模式串为 T = "abcdex". j为模式串当前位置

  • 当j=1时, next[1] = 0; //next第一个位置永远为0
  • 当j=2时, j由1到j-1范围内([1, 1]范围)只有字符 “a”, 属于其他情况, 记录next[2]=1
  • 当j=3时, j由1到j-1范围内([1, 2]范围)字符为 “ab”, 显然a不等于b, 记录next[3]=1
  • 当j=4时, j由1到j-1范围内([1, 3]范围)字符为 “abc”, 显然不存在相等的情况, 记录next[4]=1
  • 当j=5时, j由1到j-1范围内([1, 4]范围)字符为 “abcd”, 显然不存在相等的情况, 记录next[5]=1
  • 当j=6时, j由1到j-1范围内([1, 5]范围)字符为 “abcde”, 显然不存在相等的情况, 记录next[6]=1

所以 next[] = {"#", 0, 1, 1, 1, 1, 1} (next[0]用来记录next长度)

3.2、重复字符的模式串

模式串为 T = "abcabx". j为模式串当前位置

  • 当j=1时, next[1] = 0; //next第一个位置永远为0
  • 当j=2时, j由1到j-1范围内([1, 1]范围)只有字符 “a”, 属于其他情况, 记录next[2]=1
  • 当j=3时, j由1到j-1范围内([1, 2]范围)字符为 “ab”, 显然a不等于b, 记录next[3]=1
  • 当j=4时, j由1到j-1范围内([1, 3]范围)字符为 “abc”, 显然不存在相等的情况, 记录next[4]=1
  • 当j=5时, j由1到j-1范围内([1, 4]范围)字符为 “abca”, 前缀与后缀均为a, 因为p[1]=p[4]='a', 根据(p[1] ··· p[k-1] = p[j-k+1] ··· p[j-1]) 公式推导出 k=2, 记录next[5]=2
  • 当j=6时, j由1到j-1范围内([1, 5]范围)字符为 “abcab”, 前缀与后缀均为ab, 因为p[1]p[2]=p[4]p[5]='ab', 根据(p[1] ··· p[k-1] = p[j-k+1] ··· p[j-1]) 公式推导出 k=3 记录next[6]=3

所以 next[] = {"#", 0, 1, 1, 1, 2, 3} (next[0]用来记录next长度)

3.3、多个重复字符的模式串

模式串为 T = "ababaaaba". j为模式串当前位置

  • 当j=1时, next[1] = 0; //next第一个位置永远为0
  • 当j=2时, j由1到j-1范围内([1, 1]范围)只有字符 “a”, 属于其他情况, 记录next[2]=1
  • 当j=3时, j由1到j-1范围内([1, 2]范围)字符为 “ab”, 显然a不等于b, 记录next[3]=1
  • 当j=4时, j由1到j-1范围内([1, 3]范围)字符为 “aba”, 前缀与后缀均为a, 因为p[1]=p[3]='a', 根据(p[1] ··· p[k-1] = p[j-k+1] ··· p[j-1]) 公式推导出 k=2, 记录next[4]=2
  • 当j=5时, j由1到j-1范围内([1, 4]范围)字符为 “abab”, 前缀与后缀均为ab, 因为p[1]p[2]=p[3]p[4]='ab', 根据(p[1] ··· p[k-1] = p[j-k+1] ··· p[j-1]) 公式推导出 k=3, 记录next[5]=3
  • 当j=6时, j由1到j-1范围内([1, 5]范围)字符为 “ababa”, 前缀与后缀均为aba, 因为p[1]p[2]p[3]=p[3]p[4]p[5]='aba', 根据(p[1] ··· p[k-1] = p[j-k+1] ··· p[j-1]) 公式推导出 k=4 记录next[6]=4
  • 当j=7时, j由1到j-1范围内([1, 6]范围)字符为 “ababaa”, 前缀与后缀均为a, 因为p[1]=p[6]='aba', 根据(p[1] ··· p[k-1] = p[j-k+1] ··· p[j-1]) 公式推导出 k=2 记录next[7]=2
  • 当j=8时, j由1到j-1范围内([1, 7]范围)字符为 “ababaaa”, 前缀与后缀均为a, 因为p[1]=p[7]='aba', 根据(p[1] ··· p[k-1] = p[j-k+1] ··· p[j-1]) 公式推导出 k=2 记录next[8]=2
  • 当j=9时, j由1到j-1范围内([1, 8]范围)字符为 “ababaaab”, 前缀与后缀均为ab, 因为p[1]p[2]=p[7]p[8]='ab', 根据(p[1] ··· p[k-1] = p[j-k+1] ··· p[j-1]) 公式推导出 k=3 记录next[9]=3

所以 next[] = {"#", 0, 1, 1, 2, 3, 4, 2, 2, 3} (next[0]用来记录next长度)

3.4、多个重复字符的特殊模式串

再来看一个更为特殊的模式串

模式串为 T = "aaaab". j为模式串当前位置

  • 当j=1时, next[1] = 0; //next第一个位置永远为0
  • 当j=2时, j由1到j-1范围内([1, 1]范围)只有字符 “a”, 属于其他情况, 记录next[2]=1
  • 当j=3时, j由1到j-1范围内([1, 2]范围)字符为 “aa”, 前缀与后缀均为a, k=2, 记录next[3]=2
  • 当j=4时, j由1到j-1范围内([1, 3]范围)字符为 “aaa”, 前缀与后缀均为aa, k=3, 记录next[3]=3
  • 当j=5时, j由1到j-1范围内([1, 4]范围)字符为 “aaaa”, 前缀与后缀均为aaa, k=4, 记录next[3]=4

所以 next[] = {"#", 0, 1, 2, 3, 4} (next[0]用来记录next长度)

四、模式串的next数组推导-回溯

上面是讲到如何用公式去计算出next数组, 这个next数组是如何生成的呢?

4.1、非重复字符的模式串

假设:模式串为 T = "abcdex".

默认next[1] = 0, 定义i = 0, j = 1, T[i]表示前缀的单个字符, T[j]表示后缀的单个字符. 开始遍历模式串:

  • i = 0, j = 1. 此时i=0, i++, j++; 记录next[j] = next[2] = i = 1
  • i = 1, j = 2. 此时T[i]="a" T[j]="b". 两个不等. 此时i回溯到next[i] = next[1] = 0的位置
  • i = 0, j = 2. 此时i=0, i++, j++; 记录next[j] = next[3] = i = 1
  • i = 1, j = 3. 此时T[i]="a" T[j]="c". 两个不等. 此时i回溯到next[i] = next[1] = 0的位置
  • i = 0, j = 3. 此时i=0, i++, j++; 记录next[j] = next[4] = i = 1
  • i = 1, j = 4. 此时T[i]="a" T[j]="d". 两个不等. 此时i回溯到next[i] = next[1] = 0的位置
  • i = 0, j = 4. 此时i=0, i++, j++; 记录next[j] = next[5] = i = 1
  • i = 1, j = 5. 此时T[i]="a" T[j]="e". 两个不等. 此时i回溯到next[i] = next[1] = 0的位置
  • i = 0, j = 5. 此时i=0, i++, j++; 记录next[j] = next[6] = i = 1
  • i = 1, j = 6. 此时T[i]="a" T[j]="x". 两个不等. 此时i回溯到next[i] = next[1] = 0的位置
  • i = 0, j = 6. 此时i=0, i++, j++; j=7, 越界结束遍历

得到:

next[] = {"#", 0, 1, 1, 1, 1, 1}

4.2、重复字符的模式串

假设:模式串为 T = "abcabx".

默认next[1] = 0, 定义i = 0, j = 1, T[i]表示前缀的单个字符, T[j]表示后缀的单个字符. 开始遍历模式串:

  • i = 0, j = 1. 此时i=0, i++, j++; 记录next[j] = next[2] = i = 1
  • i = 1, j = 2. 此时T[i]="a" T[j]="b". 两个不等. 此时i回溯到next[i] = next[1] = 0的位置
  • i = 0, j = 2. 此时i=0, i++, j++; 记录next[j] = next[3] = i = 1
  • i = 1, j = 3. 此时T[i]="a" T[j]="c". 两个不等. 此时i回溯到next[i] = next[1] = 0的位置
  • i = 0, j = 3. 此时i=0, i++, j++; 记录next[j] = next[4] = i = 1
  • i = 1, j = 4. 此时T[i]="a" T[j]="a". 两个相等. i++, j++; 记录next[j] = next[5] = i = 2
  • i = 2, j = 5. 此时T[i]="b" T[j]="b". 两个相等. i++, j++; 记录next[j] = next[6] = i = 3
  • i = 3, j = 6. 此时T[i]="c" T[j]="x". 两个不等. 此时i回溯到next[i] = next[3] = 1的位置
  • i = 1, j = 6. 此时T[i]="a" T[j]="x". 两个不等. 此时i回溯到next[i] = next[1] = 0的位置
  • i = 0, j = 6. 此时i=0, i++, j++; j=7, 越界结束遍历 得到:

next[] = {"#", 0, 1, 1, 1, 2, 3}

4.3、next推导总结:

  1. 默认next[1] = 0
  2. 当i=0, 表示当前的比应该从头开始, 则i++, j++, next[j] = i
  3. 当T[i]==T[j], 表示两个字符相等, 则i++, j++, next[j] = i
  4. 当T[i]!=T[j], 表示两个字符不相等, 则i回溯到next[i]

五、代码实现KMP

正常情况下, 字符串是从0下标开始的, 所以首先对传过来的字符串进行修改, 变成0下边放字符串长度, 字符串下标从1开始:

typedef int Status;
/* 生成一个其值等于chars的串T */
Status StrAssign(char **T, const char *str)
{
    int len = (int)strlen(str);
    *T = malloc(len + 1);
    (*T)[0] = len;
    for (int i = 0; i < len; i++) {
        (*T)[i + 1] = str[i];
    }
    return 1;
}

接下来就需要对处理后的模式串进行获取next数组, 写一个方法来得到模式串的next数组 :

void get_next(const char *T, int *next) {
    
    int lenT = (int)strlen(T);
    int i = 0, j = 1;

    next[0] = lenT;
    next[1] = 0;

    while (j < lenT) {
        
        if (T[j] == T[i] || i == 0) {
            i++;
            j++;
            next[j] = i;
        } else {
            i = next[i];
        }
    }
}

得到next数组后, 进行与主串字符匹配:

int Index_KMP(char *S, char *T){
    char *strS = NULL;
    char *strT = NULL;

    //转换为下标从1开始
    StrAssign(&strS, S);
    StrAssign(&strT, T);

    //存放next
    int *next = (int *)malloc(sizeof(int) * (strT[0] + 1));
    //获取next
    get_next(strT, next);

    int i = 1;
    int j = 1;
    while (i <= strS[0] && j <= strT[0]) {
        if (strS[i] == strT[j] || j == 0) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    
    if (j > strT[0]) {
        return i - strT[0];
    }else{
        return -1;
    }
    
}

六、KMP算法的优化

在某些情况下, KMP得到的next数组, 一些不尽人意的地方, 例如: 当模式串为 T = "ababaaaba", 通过上述方法会得到一个next[] = "011234223". 可以发现在计算中间的重复的 'a' 的时候, 也会进行几次无用循环, 所以得想办法来优化一下这个无用循环.

当 T = "ababaaaba", j为T下标, next[] = "011234223", 定义优化的next数组为nextval

  • 当j = 1, 默认nextVal[1] = 0;
  • 当j = 2, 第2个字符是'b', next值是1, 第1位是'a', 不相等, 所以nextVal[2] = next[2] = 1
  • 当j = 3, 第3个字符是'a', next值是1, 第1位是'a', 相等, nextVal[3] = nextVal[1] = 0
  • 当j = 4, 第4个字符是'b', next值是2, 第2位是'b', 相等, nextVal[4] = nextVal[2] = 1
  • 当j = 5, 第5个字符是'a', next值是3, 第3位是'a', 相等, nextVal[5] = nextVal[3] = 0
  • 当j = 6, 第6个字符是'a', next值是4, 第4位是'b', 不相等, nextVal[6] = next[6] = 4
  • 当j = 7, 第7个字符是'a', next值是2, 第2位是'b', 不相等, nextVal[7] = next[7] = 2
  • 当j = 8, 第8个字符是'b', next值是2, 第2位是'b', 相等, nextVal[8] = nextVal[2] = 1
  • 当j = 9, 第9个字符是'a', next值是3, 第3位是'a', 相等, nextVal[9] = nextVal[3] = 0

优化的nextVal总结:

  1. 默认nextVal[1] = 0
  2. T[i] == T[j], 且++i, ++j后T[i] == T[j], 则nextVal[i] = nextVal[j]
  3. i=0时, 表示从头开始 i++, j++, 且T[i] != T[j] , 则nextVal = j
  4. T[i] == T[j], 且++i, ++j后T[i] != [j], 则nextVal = j
  5. T[i] != T[j], 不相等, 则i = next[i]