原创

KMP算法分析

简介

KMP 算法是一种改进的字符串匹配算法,KMP 算法是由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 三人提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称 KMP 算法)。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next() 函数实现,函数本身包含了模式串的局部匹配信息。

暴力匹配

有一个文本串 S 和一个模式串 P,现在要查找 P 在 S 中的位置。如果用暴力匹配的思路,

并假设现在文本串 S 匹配到 i 位置,模式串 P 匹配到 j 位置,则有:

  1. 如果当前字符匹配成功(即 Si == Pj),则 i++,j ++,继续匹配下一个字符。
  2. 如果失配(即 Si != Pj),重置 i = i - (j - 1),j = 0。相当于每次匹配失败时, i 回退,j 被置为 0。
int violenceSearch(const std::string& str, const std::string& match)
{
  int strLen = str.size(); 
  int matchLen = match.size();
  if (strLen < matchLen)
    return -1;
  int i = 0;
  int j = 0;
  while (i < strLen && j < matchLen)
  {
    if (str[i] == match[j])
    {
      i++;
      j++;
    }
    else
    {
      i = i - j + 1;
      j = 0;
    }
  }

  return j == matchLen ? i - j : -1;
}

kmp匹配

模式串ABCABD计算出部分匹配表,匹配表如下:

字符

A

B

C

A

B

D

匹配值

0

0

0

1

2

0

/**
 * 部分匹配值就是前缀和后缀的最长共有元素的长度。假设一个字符串 "hello",它的前缀有 h、he、hel、hell,
 * 它的后缀有 ello、llo、lo、o。
 * 
 * 假设模式字符串为:ABCAB
 * 
 * A 没有前缀和后缀,公有元素长度为 0
 * AB 的前缀有 A,后缀有 B,公有元素长度为 0
 * ABC 的前缀有 A、AB,后缀有 BC、C,公有元素长度为 0
 * ABCA 的前缀有 A、AB、ABC,后缀有 BCA、CA、A,公有元素长度为 1
 * ABCAB 的前缀有 A、AB、ABC、ABCA,后缀有 BCAB、CAB、AB、B,公有元素长度为 2
 * ABCABD 的前缀有 A、AB、ABC、ABCA、ABCAB,后缀有 BCABD、CABD、ABD、BD、D,公有元素长度为 0
 * 所以 ABCABD 中每个字符对于的匹配值分别为 0、0、0、1、2、0。
 */

std::vector<int> getNext(const std::string &match)
{
    int k = 0;
    int len = match.size();
    std::vector<int> next(len, 0);
    for (int i = 1; i < len; ++i)
    {
        if (k > 0 && match[k] != match[i]) 
            k = next[k - 1];
        if (match[k] == match[i])
            k++;
        next[i] = k;
    }
    return next;
}

int kmp(const std::string &str, const std::string &match)
{
    std::vector<int> next = getNext(match);
    int k = 0;
    for (int i = 0; i < str.size(); ++i)
    {
        if (k > 0 && match[k] != str[i])
            k = next[k];
        if (match[k] == str[i])
            k++;
        if (k == match.size())
            return i - k + 1;
    }
    return -1;
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于zmq RPC简单C++实现

    需要启动rpc_server,然后启动rpc_client,请求Strcat和add返回结果:

    evenleo
  • 归并快排算法比较及求第K大元素

    核心思想:将数组从中间分成前后两部分,然后对前后两部分分别进行排序,再将排序好的两个部分有序合并在一起,这样整个数组有序。全文图示来源于王争的《数据结构和算法之...

    evenleo
  • sds数据结构分析-redis源码阅读笔记(1)

    evenleo
  • 聊聊dubbo-go的tracingFilter

    dubbo-go-v1.4.2/filter/filter_impl/tracing_filter.go

    codecraft
  • 聊聊dubbo-go的tracingFilter

    dubbo-go-v1.4.2/filter/filter_impl/tracing_filter.go

    codecraft
  • 外观模式

    一、简介 1、外观模式为子系统中的一组接口提供一个统一的高层接口,这一接口使得子系统更加容易使用。 2、举例 :房间里有3盏灯,每一盏灯都有一个开关控制它的开和...

    用户1215536
  • dplyr包summarize的使用

    cyl有4,6,8三种取值,而gear有3,4,5三种取值,应该一共有9组,但我们这里只有8组,原因是cyl=8,gear=4的没有,默认不填补缺失值就会被 d...

    爱学习的小明明
  • 展望2020 | 中国文旅八大趋势研判

    ? 2019年是寒冷坎坷的一年。全球经济在艰难中逆风前行,国内经济内外需求疲软、投资增速放缓、出口量走低,经济下行压力加大。在此背景下,互联网、房地产、金融企...

    腾讯文旅
  • 深入理解Java常用类----String(二)

         上篇介绍了String类的构造器,获取内部属性等方法,最后留下了最常用的局部操作函数没有介绍,本篇将接着上篇内容,从这些最常见的函数的操作说起,看看我...

    Single
  • 吴恩达对话LeCun:神经网络跌宕四十年

    最近,这位AI领域的传奇大牛,接受了另一位大牛吴恩达的视频专访。在这次对话中,LeCun回顾了卷积神经网络、反向传播的历史,以及他如何从一个默默无闻的“法国小孩...

    量子位

扫码关注云+社区

领取腾讯云代金券