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

相关文章

来自专栏cs

c++那些事儿4.0 多态

---- 相关知识点 多态: 向不同对象发送一个消息,不同的对象接收会产生不同的行为。 a.静态多态性。 函数重载,最经典就是构造函数重载...

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

Codeforces 791A Bear and Big Brother(暴力枚举,模拟)

A. Bear and Big Brother time limit per test:1 second memory limit per test:256 m...

41190
来自专栏水击三千

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

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

254100
来自专栏企鹅号快讯

Python这些问题你都会吗?

距离Python圣诞学习狂欢夜 还有4天 点击进入详细了解 final作用域的代码一定会被执行吗? 正常的情况下,finally作用域的代码一定会被执行的,不管...

24350
来自专栏idba

Python的map函数

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

9320
来自专栏xingoo, 一个梦想做发明家的程序员

KMP算法初探

[edit by xingoo] kmp算法其实就是一种改进的字符串匹配算法。复杂度可以达到O(n+m),n是参考字符串长度,m是匹配字符串长度。 传统的算法,...

19360
来自专栏Python小屋

Python计算整数阶乘的几种方法比较

问题本身很简单,主要是通过这个小问题来演示Python的一些用法,例如测试代码运行时间、函数嵌套定义等等。 from time import time from...

82970
来自专栏黑泽君的专栏

throws 与 throw

/* * 有些时候,我们是可以对异常进行处理的,但是又有些时候,我们根本就没有权限去处理某个异常。 * 或者说,我处理不了,我就不处理了。 * 为了解决出...

23920
来自专栏林德熙的博客

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

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

8110
来自专栏Fish

两天了解scala

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

21090

扫码关注云+社区

领取腾讯云代金券