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

相关文章

来自专栏web前端教室

javascript 数组的深复制和浅复制

这段时间忙的我是欲仙欲死,导致公众号断更了好几天。 但收获也是巨大的,对于JS的一些应用有了一些新的理解,以后我慢慢写出来。 今天简单的写一个javascrip...

1865
来自专栏javathings

什么是 default 方法

Java 设计者希望能在 List 上提供一个 forEach 方法,例如可以 list.forEach(System.out::println) 而 L...

632
来自专栏calmound

String to Integer (atoi)

问题:将字符窜转换成数字 分析:感觉题目不难,但是细节很多,容易想不到 1.数字前面有空格 如s=“    123456” 2.数字前出现了不必要或多于的字符导...

2638
来自专栏C/C++基础

C/C++编码规范

对于变成人员,良好的编程风格是提高程序可靠性和效率非常重要的手段。而编码规范就是对编程风格最好的约束保障。 严格遵守编码规范方便代码的交流和维护,利于提高代...

882
来自专栏微信公众号:Java团长

Java String 对 null 对象的容错处理

第一句相信大家都会容易理解,这是类型初始化的基础知识,但是第二句就让我很疑惑:为什么打印一个 null 对象不会抛出异常?带着这个疑问,我开始了解惑之旅。下面我...

582
来自专栏工科狗和生物喵

【计算机本科补全计划】C++ Primer:String Vector标准库及迭代器的使用

正文之前 今天帮学妹选了一天的电脑配件,然后从中领悟:坐看狗东黑我钱,任他涨价我不动!!最后果断的用学妹的钱冲了个Plus,然后领了一堆券,最后学妹还省了30块...

35810
来自专栏王磊的博客

《JavaScript权威指南》——JavaScript核心

前言 这本由David Flanagan著作,并由淘宝前端团队译的《JavaScript权威指南》,也就是我们俗称的“犀牛书”,算是JS界公认的“圣经”了。本书...

3459
来自专栏较真的前端

关于数组的前端面试题,你是否都能答对?

2183
来自专栏JAVA高级架构

Java面试题合集

1.抽象类与接口的区别是什么? 一个类可以实现多个接口,但是只能继承以及抽象类。类如果要实现一个接口,它必须要实现接口声明的所有方法。但是,类可以不实现抽象类声...

33410
来自专栏java思维导图

你真的懂Java中的String、StringBuilder和StringBuffer吗?

相信String这个类是Java中使用得最频繁的类之一,并且又是各大公司面试喜欢问到的地方,今天就来和大家一起学习一下String、StringBui...

1022

扫码关注云+社区