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

相关文章

来自专栏idba

Python的map函数

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

662
来自专栏闻道于事

Java之异常处理

Java异常处理 异常:异常就是Java程序在运行过程中出现的错误。 异常由来:问题也是现实生活中一个具体事务,也可以通过java 的类的形式进行描述,并封装成...

2816
来自专栏机器学习实践二三事

python基础----函数参数

函数参数 (1)直接传入 >>def test(a,b): return a+b >>test(3, 4) (2)默认参数 >> def add(a...

18210
来自专栏企鹅号快讯

Python这些问题你都会吗?

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

1945
来自专栏cs

c++那些事儿4.0 多态

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

3199
来自专栏林德熙的博客

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

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

491
来自专栏Fish

两天了解scala

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

1949
来自专栏黑泽君的专栏

throws 与 throw

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

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

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

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

3619
来自专栏赵俊的Java专栏

Python 函数

1504

扫码关注云+社区