史上最透彻的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 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

Python正则表达式指南

本文介绍了Python对于正则表达式的支持,包括正则表达式基础以及Python正则表达式标准库的完整介绍及使用示例。本文的内容不包括如何编写高效的正则表达式、如...

1935
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版3.6节栈布局之gcc内嵌关键字

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

581
来自专栏林德熙的博客

win10 uwp 如何判断一个对象被移除

有时候需要知道某个元素是否已经被移除,在优化内存的时候,有时候无法判断一个元素是否在某个地方被引用,就需要判断对象设置空时是否被回收。 本文告诉大家一个简单的方...

561
来自专栏技术之路

typedef 和define的区别

总结一下typedef和#define的区别 1.概念   #define 它在编译预处理时进行简单的替换,不作正确性检查。它是预处理指令。   typedef...

1867
来自专栏赵俊的Java专栏

Python 函数

2154
来自专栏Spark学习技巧

Scala语法基础之隐式转换

一,简介 从类型S到类型T的隐式转换由具有函数类型S => T的隐式值定义,或者通过可转换为该类型的值的隐式方法来定义。隐含转换适用于两种情况: 1),如果表达...

2419
来自专栏idba

Python的map函数

一 简介 Python 内置了很多非常有用的函数 比如map() ,reduce(),filter(),还有lambda。熟练应用这些函数可以在写python...

742
来自专栏Fish

两天了解scala

最前面的话 因为spark的源语言是scala,所以,为了看懂spark的操作并且为了以后看spark源码做准备,先看scala还是很有必要的。另外这里主要是看...

2009
来自专栏猿人谷

《C++ primer》--第1,2章小结

 1、变量初始化:  定义变量时,应该给变量赋初始值,除非确定将变量用于其他意图之前会覆盖这个初值。如果不能保证读取变量之前重置变量,就应该初始化变量。变量...

20410
来自专栏水击三千

浅谈JavaScript的函数表达式(递归)

  递归函数,在前面的博客中已经简单的介绍了。递归函数是一个通过函数名称在函数内部调用自身的函数。如下: 1 function fac(num){ 2 ...

22510

扫码关注云+社区