史上最透彻的KMP算法讲解

作 者:柳行刚 编 辑:李文臣

1

字符串匹配是经典的KMP算法。下面以字符串"BBC ABCDAB ABCDABCDABDE"为例,查找是否包含串"ABCDABD"?

图一

2

首先如上图,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜词"ABCDABD"的第一个字符,B与A不相等,所以后移动。

图二

3

上图中,D与空格不相等,但是它有前缀AB与后缀AB相当,KMP的思想就是利用最长的公共前缀与最长公共后缀相等,来加快每次不相等时移动的距离,来提高搜索效率。

4

要做到这一点,就是要生成一个next匹配数组,next匹配数据来决定匹配的最大长度。如图二。查next数组可知,最后一个匹配字符B对应的"部分匹配值"为2,因此后移动的位数:移动位数 = 已匹配的字符数 - 对应的部分匹配值。因为 6 - 2 等于4,所以将搜索词向后移动4位。

下面是next数组和匹配算法参照代码。

精彩内容

#include <cstring>
using namespace std;

const int N = 1000002;
int next[N];
char S[N], T[N];
int slen, tlen;

void getNext()
{
    int j, k;
    j = 0; k = -1; next[0] = -1;
    while(j < tlen)
        if(k == -1 || T[j] == T[k])
            next[++j] = ++k;
        else
            k = next[k];

}
/*
返回模式串T在主串S中首次出现的位置
返回的位置是从0开始的。
*/
int KMP_Index()
{
    int i = 0, j = 0;
    getNext();

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

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-10-23

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PHP技术

PHP 排序算法实现讲解

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序 算法在很多领域得到相...

2605
来自专栏我和PYTHON有个约会

15. 程序编程进阶:函数的返回值

函数中代码块执行的结果,如果我们后面的代码中需要用到,就需要函数返回我们执行的结果,就是需要返回值;

932
来自专栏前端黑板报

一个数字截取引发的精度问题(二)

上篇文章只是简单介绍了Number的 toFixed 方法,周末抽时间把 Number 里的一些方法又看了一下,其中有个方法引起我的注意: Number.pro...

1836
来自专栏数据结构与算法

2039. 树的统计

输入文件:counttree.in   输出文件:counttree.out 简单对比 时间限制:1 s   内存限制:128 MB 【题目描述】 关于...

33510
来自专栏小樱的经验随笔

Vijos P1786 质因数分解【暴力】

质因数分解 背景 NOIP2012普及组第一题 描述 已知正整数n是两个不同的质数的乘积试求出较大的那个质数。 格式 输入格式 输入只有一行包含一个正整数n。 ...

2944
来自专栏灯塔大数据

技术 | Python从零开始系列连载(七)

导读 上一期学习了Python程序的基本控制流程,相信大家都已经熟悉啦,我们这一期就来学习Python特色数据类型(列表)吧! Python特色数据类型(列表)...

32910
来自专栏云瓣

正则&highlight高亮实现(干货)

写完正则表达式以后在浏览器上检测实在是不方便,于是就写了一个JS正则小工具,大大地提高了学习效率。学习之余用正则实现了一个highlight高亮demo,欢迎交...

32712
来自专栏Python小屋

Python中的偏函数和函数柯里化

偏函数(partial)和函数柯里化(currying)是函数式编程中常用的技术。有时候我们在复用已有函数时可能需要固定其中的部分参数,这除了可以通过默认值参数...

2544
来自专栏zaking's

用js来实现那些数据结构08(链表02-双向链表)

  其实无论在任何语言中,一种数据结构往往会有很多的延伸和变种以应对不同场景的需要。其实前面我们所学过的栈和队列也是可以用链表来实现的。有兴趣的小伙伴可以自己尝...

2676
来自专栏Java3y

希尔排序就这么简单

一、希尔排序介绍 来源百度百科: 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort...

3946

扫描关注云+社区