KMP算法的时间复杂度与next数组分析

太过爱你忘了你带给我的痛 2023-06-02 09:18 5阅读 0赞

## 一、什么是 KMP 算法 ##

KMP 算法是一种改进的字符串匹配算法，用于判断一个字符串是否是另一个字符串的子串

## 二、KMP 算法的时间复杂度 ##

O(m+n)

## 三、Next 数组 - KMP 算法的核心 ##

KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next() 实现

### 1、**next 数组**： ###

长度与字符串长度一致，每个位置存储对应字符的最长匹配长度

### 2、next 数组通过遍历子字符串中"前缀"和"后缀"的最长的共有元素的长度来获得 ###

![1731684-20190823122047283-427769642.png][]

例如 ABCDABD，得到的 next 数组为 \[0,0,0,0,1,2,0\]

简单地观察一下就会发现，该算法会进行最少 21 次的字符串判断，这还是在不考虑字符串匹配的时间消耗，光此一项的时间复杂度就是

O(n) = (n(n - 1)) /2 = n² / 2 + n / 2 = n²

在加上匹配字符串，就是m + n²显然大于KMP算法的时间复杂度m + n

### 3、next数组通过加入回溯法，在遍历子字符串时，判断逐步判断字符是否相同 ###

例如：

j=0,    i=1,    (j=0),     next=[0,1];
    j=1,    i=2,    (A!=B),    j=next[0];
    j=0,    i=2,    (j=0),    next=[0,1,1];
    j=1,    i=3,    (A!=C),    j=next[0];
    j=0,    i=3,    (j=0),    next=[0,1,1,1];
    j=1,    i=4,    (A!=D),    j=next[0];
    j=0,    i=4,    (j=0),    next=[0,1,1,1,1];
    j=1,    i=5,    (A=A),    next=[0,1,1,1,1,2];
    j=2,    i=6,    (B=B),    next=[0,1,1,1,1,2,3];

总共运行9次就获得了next数组，算法时间复杂度是O(n) = n

### 4、对于两个next数组的用法也有区别 ###

//1.阮
    //i值即移动位数：移动位数 = 已匹配的字符数 - 对应的部分匹配值
    function kmp(s1, s2) {
        var next = getNext(s2);
        var j = 0;
        for (var i = 0; i < s1.length;) {
            for (; j < s2.length; j++) {
                if (s1.charAt(i + j) != s2.charAt(j)) {
                    i += j > 0 ? (j - next[j - 1]) : 1;
                    j = next[j > 0 ? j - 1 : 0];
                    break;
                } else if (j == s2.length - 1) {
                    return i;
                }
            }
        }
        return -1;
    }
     
    //2.程
    function kmp2(s1, s2) {
        var j = 0;
        var next = get_next(s2);
        for (var i = 0; i < s1.length;) {
            for (; j < s2.length; j++) {
                if (s1.charAt(i) != s2.charAt(j)) {
                    j == 0 ? i++ : true;
                    j = next[j > 0 ? j - 1 : 0];
                    break;
                } else if (j == s2.length - 1) {
                    return i - j;
                }
                i++;
            }
        }
        return -1;
    }
     
    //3.也正是由于i值的大小随着j值的大小进行改变，
    //  使得被查找字符串仅被遍历一次即可得到解。
    //  故时间复杂度为m
    //  加上获得next数组的时间复杂度就是kmp算法的总时间复杂度m+n；

转载于:https://www.cnblogs.com/Leophen/p/11399277.html

[1731684-20190823122047283-427769642.png]: /images/20230601/2cfdeb68c746429d8e4828f2042986c1.png