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

一、什么是 KMP 算法

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

二、KMP 算法的时间复杂度

O(m+n)

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

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

1、next 数组

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

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

例如 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数组通过加入回溯法,在遍历子字符串时,判断逐步判断字符是否相同

function get_next(s) {
    var i = 1;
    var j = 0;
    var next = [0];
    while (i < s.length) {
        if (j == 0 || s.charAt(i - 1) == s.charAt(j - 1)) {
            i++;
            j++;
            next.push(j);
        } else {
            j = next[j - 1];
        }
    }
    return 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;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏架构师进阶

Spring Boot集成Spring Data Jpa

之前写过spring data jpa 入门,Spring Boot 使用Jpa,很简单,也很方便,这里简单介绍一下。

10730
来自专栏架构师进阶

Spring-RestTemplate实战

这里总结一下,怎么用代码发起HTTP请求:Post、Get等。之前类似的请求都是用Postman。RestTemplate网上教程也是很多,但是编程就是要多实战...

13740
来自专栏三言两语

JQuery选择器和JQuery包装集

(本文年代久远,请谨慎阅读)今天学习了JQuery的一些基本用法,包括JQuery选择器和JQuery包装集;

8520
来自专栏实时计算

Vimtutor中文版

=============================================================================== ...

20350
来自专栏三言两语

Scala的基础概念

例如:调用 def Add(y:Int) = x + y 其结果为xy之和,并且调用之后没有引起x值的变换,没有副作用 所以,Add函数没有副作用

9230
来自专栏架构师进阶

Error:(1, 1) java: 非法字符: '\ufeff'

运行mvn compile也是报同样的错误。感觉好奇怪啊,仔细看看对应的行没啥问题啊。我用的工具是IntelliJ IDEA 2016.3(64),同样的代码在...

53820
来自专栏秘籍酷

嵌入式(触摸板库tslib的编译和配置)

作为基本输入设备,触摸板几乎是交互式嵌入式系统的标配。当我们知道了可以通过设备节点读取触摸板数据后,我们需要进一步优化这些直接获取的原生数据,比如去抖、消噪、校...

12230
来自专栏秘籍酷

C++若是军火库,继承就是挺重机枪

继承的本质是代码重用,不再重复设计已有的东西。比如猴子有眼耳鼻舌等器官,有摸爬滚打等行为,而人是一种猴子(科学术语强迫症患者,以及生物科学工作者请绕行,这里只是...

11830
来自专栏实时计算

机器学习(六)--------神经网络(Neural Networks)

无论是线性回归还是逻辑回归都有这样一个缺点,即:当特征太多时, 计算的负荷会非常大。 比如识别图像,是否是一辆汽车,可能就需要判断太多像素。 这时候就需要...

9240
来自专栏秘籍酷

C语言(函数指针和指针函数)

经翻阅小学五年级语文课本得知,一个短语中的最后部分,是这个短语的中语,其余部分是定语(修饰语)。也就是说,以上短语相当于:

28420

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励