用JS写KPM算法

winterdawn 发布于2019-08-20 19:08 / 2544人阅读

摘要：通过观察发现，如果匹配字符串中有相同的子字符串，那么的变化会有所不同。所以这个值的变化跟目标字符串没什么关系，只跟自己的子字符串的重复性有关。的两侧子字符串相等，所以这时候倒数两位位位代码量不多但理解起来有点困难反正我理解了很久。

最近公司启动小程序项目中，在搜索模块有这么个功能需求：当用户输入搜索内容时实时地请求服务器得到一组较高匹配度的搜索关键字，在这些关键字中高亮显示用户的匹配输入。

例如输入“中国”
搜索关键字为“中国共产党”

那我就想到了KPM算法，就打开《大话数据结构》这本书来看看KPM到底是什么东西，倒腾了很久，终于对KPM算法有一点点点点点点了解，就来记录一下。

传统的字符串匹配算法

传统的字符串匹配算法是这样子的：当目标字符串和匹配字符串在匹配过程中发生失配，目标字符串下标和匹配字符串下标都要回溯，这会导致一些不必要的匹配判断，举个栗子。

当匹配到第4位的时候，偶哦匹配失败，那么将会从下面的位置开始匹配

但是我们明眼看去，很明显是多余匹配判断了吗。
对没错，传统的匹配算法会只是很简单的匹配回溯匹配回溯，时间复杂度为O((n-m)*m)，导致很多的匹配判断是多余的，那么接下来的KPM算法就是解决这个笨重的问题的。

KPM算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
注：一下i代表目标字符串的下标，j代表匹配字符串的下标。
刚才讲到，我们的KPM算法就是为了让这没必要的回溯发生，那么i不可变小，就只考虑变化j值了。通过观察发现，如果匹配字符串中有相同的子字符串，那么j的变化会有所不同。所以这个j值的变化跟目标字符串没什么关系，只跟自己的子字符串的重复性有关。

next[j] = -1 // 当j == 0时
        = max{k|0
例如：
j:       0 1 2 3 4
P:       A B A B C
next[j]:-1 0 0 1 2   

说白了就是j前的子字符串的重复字符有多少个，那么next[j]就是重复字符串个数。
next数组的作用就是KPM算法j值的回溯方案。
还是上面那么例子。当i = 4, j = 4时C !== X ，那么这个时候j = next[j] = 2，所以只需进行target[i(为4)]和pattern[j(为2)]的判断，而pattern[0]和pattern[1]分别的判断省略掉了。
说了那么多太干了，贴个代码先。
var target = "ababxababc"
var pattern = "ababc"

function getKPMNext(str) {
    var i, j;
    var next = [];

    next[0] = -1;
    i = 0; j = -1;

    while(i < str.length - 1) {
        if (j == -1 || str[i] == str[j]) {
            next[++i] = ++j;
        } else {
            j = next[j];
        }
    }
    return next;
}

// j = next[j] next[j]的两侧子字符串相等，所以这时候str[i] == str[j] 倒数两位== 4 5位 == 1 2位
console.log(getKPMNext("abxabaabxabxa"))

代码量不多但理解起来有点困难（反正我理解了很久T_T）。j = -1的时候就是上述next数组在其他情况。
当str[i] == str[j]的时候，那么i和j就很愉快地手牵手地前进。
当str[i] != str[j]的时候，那么j就要回溯。
然后就是KPM算法的主体了
function KPMMatch(target, pattern) {
    var i = 0, j = 0;
    var next = getKPMNext(pattern);

    while (i < target.length && j < pattern.length) {
        if (j == -1 || target[i] == pattern[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    if (j >= pattern.length) {
        return i - j;
    }
    return -1;
}

当失配时j回溯，相对于传统匹配省掉了不必要的匹配。

云服务器 GPU云服务器用c语言写归并算法 js 写一个组合算法用js写自己的网站 KPM

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/85190.html

【Electron】酷家乐客户端开发实践分享 — 下载管理器

摘要：作者钟离，酷家乐客户端负责人原文地址酷家乐客户端下载地址文章背景在酷家乐客户端在改版成功后，我们积累了许多的宝贵的经验和最佳实践。作者：钟离，酷家乐PC客户端负责人原文地址：https://webfe.kujiale.com/electron-ku-jia-le-ke-hu-duan-kai-fa-shi-jian-fen-xiang-jin-cheng-tong-xin/酷家乐客...

yuxue 2019-08-02 15:18 评论0 收藏0
【Electron】酷家乐客户端开发实践分享 — 下载管理器

摘要：作者钟离，酷家乐客户端负责人原文地址酷家乐客户端下载地址文章背景在酷家乐客户端在改版成功后，我们积累了许多的宝贵的经验和最佳实践。作者：钟离，酷家乐PC客户端负责人原文地址：https://webfe.kujiale.com/electron-ku-jia-le-ke-hu-duan-kai-fa-shi-jian-fen-xiang-jin-cheng-tong-xin/酷家乐客...

褰辩话 2019-08-23 18:07 评论0 收藏0
前端是有多难？

摘要：我之前从来没想过高阶函数怎么在里面用，直到看了源码吃了一惊，卧槽，还能这么写还有说烂了的柯里化。然而也加重了前端的负担。毕竟和前端靠的近，人家问起来自己不会多尴尬。好了，一个前端工程师做到这份上也算是仁至义尽了。最近感觉追不动前端的发展了，写篇文章感叹一下。 HTML 我知道有一些学校会教一些简单的网页制作，就是用 Dreamweaver 点一点的那种。大多也会留作业，最后交作业的时...

habren 2019-08-21 14:21 评论0 收藏0