数据结构

数据结构(11)-KMP算法

2020-05-03  本文已影响0人  xxxxxxxx_123

KMP算法是由三位计算机科学家D.E.Knuth、J.H.Morrs、VR.Pratt发表的一个模式匹配算法。和BM算法类似，KMP算法也在减少没有必要的字符匹配，不过KMP算法的侧重点是在已匹配的前缀

思路

首先，我们来看一个例子，主串abcdefgab，模式串abcdex。在第一轮比较的时候，KMP算法和BF算法一样都是从首字母开始匹配。

abcdefgab
abcdex

第一轮匹配成功，则开始第二轮比较第二个字符，以此类推。

kmp01.png

如果模式串后续不存在与首字母b相匹配的字符，那么我们可以忽略后面四次比较，直接把模式串移动到第六个字母开始匹配，即②③④⑤都是可以忽略的。之所以保留第⑥步是应为我们知道T[0]≠T[5]，但是不能确定T[1]≠S[5]。

如果存在重复字符又会怎么样呢？我们再来看一个例子，主串为abcabcabc、模式串为abcabx。比较如下：

kmp02.png

因为模式串中前五个字符abcab中，最前面两个字符ab和最后面两个字符ab是相等的，所以上述④⑤两个步骤也可以省略。

对比这两个例子，我们发现去掉这些不必要的比较之后，i值就不会再回溯，那么我们就需要考虑j的变化了。而且我们也可以发现j的变化，其实和模式串中有没有相等的前缀后缀来确定的，和主串并没有关系。此时引入一个重要的概念，next数组。

next数组

next数组是一个一维的整形数组，它是KMP算法的核心，只要得到这个数组，我们就能确定每次遍历模式串如何进行回溯。那么如何来推导这个数组呢？

因为next数组是针对模式串的，那么next的长度就是模式串的长度。next数组分为两种情况，一种是字符串的第一个位置保存的是字符串的长度而非内容，第二种是第一个位置就是字符串的内容。需要注意的是，next数组对应的是当前字符之前的子串中的前后缀的匹配情况。

非标准串

字符串内容从下表为1开始，即第一个位置保存的是字符串的长度。

我们可以得到如下定义：

next.png

需要注意的是next数组默认从1开始，我们来做一下next数组的推导：

  1. abcdex
  1. abcabx
  1. ababaaaba
  1. aaaaaaaab可以得出next[j] = 012345678

那么next数组如何用代码实现呢？如果我们遍历模式串找到每一个子串，然后再来对比子串对应的前后缀元素，来确定相等的个数，通过这样的方式来求next数组是比较麻烦的。通过指针回溯的方法相对来说要简单很多。下面我们来看看如果通过指针回溯的方式求出next数组：

代码实现如下：

//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void getNexts(String T,int *next){
    int i = 1;
    int j = 0;
    next[1] = 0;
    
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            // i==0的时候说明回溯的时候没有匹配的 也就是不存在相等的前后缀
            i += 1;
            j += 1;
            next[i] = j;
        } else {
            // 如果字符不相同,则j值回溯;
            // 回溯到上一个比较位置 如果还不相同就继续回溯 
            // 一直回溯到j=1的时候值如果还是没有那就说明整个子串中没有相对应的前后缀元素 则直接将next的值置为1
            j = next[j];
        }
    }
}

得出了next数组，那我们就可以使用它来做模式串匹配了。匹配的过程就和BF算法一样了，唯一不同的地方就是当字符出现不匹配的时候，主串不需要回溯，回溯的是模式串。

// T[0] 和 S[0] 存储的是字符串T与字符串S的长度
int KMP(String S, String T) {
    if (S == NULL || T == NULL || T[0] == 0 || S[0] <= T[0]) {
        return 0;
    }
    
    int i = 1;
    int j = 1;
    int *next = (int *)malloc(sizeof(int) * (T[0] + 1));
    getNexts(T, next);

    //若i小于S长度并且j小于T的长度是循环继续;
    while (i <= S[0] && j <= T[0]) {
        //如果两字母相等则继续,并且j++,i++继续比较
        if(j == 0 || S[i] == T[j]) {
            i += 1;
            j += 1;
        } else {
            //如果不匹配时,j回溯到next中对应的位置
            j = next[j];
        }
    }
    
    if (j > T[0]) {
        return i - T[0];
    } else {
        return -1;
    }
}

从代码可以看出，KMP算法的时间复杂度为O(m+n)，相比于BF算法，还是有比较大的提高的。但是上述实现中还是有缺陷的，比如主串S= aaaabcde，模式串T= aaaaax，next数组是012345。匹配的过程如下：

kmp03.png

其实，在i=5, j=5的时候可以得到b≠a，所以②③④⑤这几步的回溯是没有意义的。由于模式串的前几位字符都是相等的，所以我们可以用next[1]的值去替代后几位next[j]的值，从而达到优化的目的。

我们推导一下新数组nextval的实现：

  1. 模式串aaaaax的next[j] = 012345
  1. 模式串abcabx的next[j] = 011123

优化后代码如下：

void getNextvals(String T,int *nextval){
    int i = 1;
    int j = 0;
    nextval[1] = 0;
    
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            i += 1;
            j += 1;
            if (T[i] != T[j]) {
                nextval[i] = j;
            } else {
                // 当前字符和前缀字符相同，则把前缀字符的nextval值赋给当前字符
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
}

通过执行代码，我们可以看到示例kmp("abcddddabcabx", "abcabx")在优化前会循环14次，优化之后会循环13次，而示例kmp("aaaaabaabaaaaax", "aaaaax")在优化前会循环22次，优化之后会循环16次。

标准串

字符串第一个位置元素即为字符串的内容。可以得到如下定义：

next[j] = \begin{cases} -1， & \text{当j=0时} \\ k， &\text{子串中前后缀相等的最大元素数} \\ 0， & \text{子串中不存在相等的前后缀元素} \end{cases}

这个推导过程和上面的一样，就不在此赘述了。比如issip得到next数组为-10001。

下面我们来看一下代码实现：

void getNexts(char *T, int *next, int tlen) {
    int i = 0;
    int j = -1;
    // 默认next[0] = -1
    next[0] = -1;

    while (i < tlen - 1) {
        if (j == -1 || T[j] == T[i]) {
            j++;
            i++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int kmp(char *S, char *T) {
    int slen = (int)strlen(S);
    int tlen = (int)strlen(T);
    if (tlen == 0) {
        return 0;
    }
    if (tlen > slen) {
        return -1;
    }
    
    int *next = (int *)malloc(sizeof(int) * tlen);
    getNexts(T, next, tlen);
    
    int i = 0;
    int j = 0;
    while (i < slen && j < tlen) {
        if (S[i] == T[j]) {
            if (j == tlen - 1) {
                return i - tlen + 1;
            }
            j += 1;
            i += 1;
        } else {
            if (next[j] >= 0) {
                j = next[j];
            } else {
                // 模式串起始位置不相等的话 主串需要移动一位 模式串需要回溯到第一个字符位置
                j = 0;
                i += 1;
            }
        }
    }
    
    return -1;
}

其优化和上面类似，就不赘述了。

总结

KMP算法的通过添加辅助数组next，减少了模式匹配中不必要的回溯。其空间复杂度为next数组的长度，即O(n)，其时间复杂度为生成next数组时的O(n)加上遍历主串时的O(m)，即O(m+n)。KMP算法的核心在于计算next数组，而计算next数组的关键则是模式串子串中最长可匹配的前后缀。

上一篇下一篇

猜你喜欢

热点阅读