字符串匹配的kmp算法_多字符串匹配

字符串匹配的kmp算法_多字符串匹配一、背景  给定一个主串(以S代替)和模式串(以P代替),要求找出P在S中出现的位置,此即串的模式匹配问题。  Knuth-Morris-Pratt算法(简称KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(DonaldErvinKnuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。  在继…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、背景

  给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题。

  Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。

  在继续下面的内容之前,有必要在这里介绍下两个概念:真前缀真后缀

这里写图片描述

  由上图所得, “真前缀”指除了自身以外,一个字符串的全部头部组合;”真后缀”指除了自身以外,一个字符串的全部尾部组合。

二、KMP字符串匹配算法

1、算法流程

(1)

  首先,主串”BBC ABCDAB ABCDABCDABDE”的第一个字符与模式串”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以模式串后移一位。

这里写图片描述

(2)

  直到主串有一个字符,与模式串的第一个字符相同为止。

这里写图片描述

(3)

  接着比较主串和模式串的下一个字符,直到主串有一个字符,与模式串对应的字符不相同为止。

这里写图片描述

  一个基本事实是,当空格与D不匹配时,你其实是已经知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,而是继续把它向后移,这样就提高了效率。

(4)

  怎么做到这一点呢?可以针对模式串,设置一个跳转数组int next[],这个数组是怎么计算出来的,后面再介绍,这里只要会用就可以了。

这里写图片描述

(5)

  已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。根据跳转数组可知,不匹配处D的next值为2,因此接下来从模式串下标为2的位置开始匹配。

这里写图片描述

  因为空格与C不匹配,C处的next值为0,因此接下来模式串从下标为0处开始匹配。

(6)

这里写图片描述

  因为空格与A不匹配,此处next值为-1,表示模式串的第一个字符就不匹配,那么直接往后移一位。

(7)

这里写图片描述

  逐位比较,直到发现C与D不匹配。于是,下一步从下标为2的地方开始匹配。

(8)

  逐位比较,直到模式串的最后一位,发现完全匹配,于是搜索完成。

这里写图片描述

2、next数组是如何求出的

  next数组的求解基于“真前缀”和“真后缀”,即next[i]等于P[0]…P[i – 1]最长的相同真前后缀的长度(请暂时忽视i等于0时的情况,下面会有解释)。

这里写图片描述

这里写图片描述
这里写图片描述

  那么,为什么根据最长相同真前后缀的长度就可以实现在不匹配情况下的跳转呢?举个代表性的例子:假如i = 6时不匹配,此时我们是知道其位置前的字符串为ABCDAB,仔细观察这个字符串,首尾都有一个AB,既然在i = 6处的D不匹配,我们为何不直接把i = 2处的C拿过来继续比较呢,因为都有一个AB啊,而这个AB就是ABCDAB的最长相同真前后缀,其长度2正好是跳转的下标位置。

3、next数组的实现

void cal_next(string &str, vector<int> &next)
{
    const int len = str.size();
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < len - 1)
    {
        if (k == -1 || str[j] == str[k])
        {
            ++k;
            ++j;
            next[j] = k;//表示第j个字符有k个匹配(“最大长度值” 整体向右移动一位,然后初始值赋为-1)
        }
        else
            k = next[k];//往前回溯
    }
}

(1)i和j的作用

  i和j就像是两个”指针“,一前一后,通过移动它们来找到最长的相同真前后缀。

(2)if…else…语句里做了什么?

这里写图片描述

  假设i和j的位置如上图,由next[i] = j得,也就是对于位置i来说,区段[0, i – 1]的最长相同真前后缀分别是[0, j – 1]和[i – j, i – 1],即这两区段内容相同

  按照算法流程,if (P[i] == P[j]),则i++; j++; next[i] = j;;若不等,则j = next[j],见下图:

这里写图片描述

  next[j]代表[0, j – 1]区段中最长相同真前后缀的长度如图,用左侧两个椭圆来表示这个最长相同真前后缀,即这两个椭圆代表的区段内容相同;同理,右侧也有相同的两个椭圆。所以else语句就是利用第一个椭圆和第四个椭圆内容相同来加快得到[0, i – 1]区段的相同真前后缀的长度。

  j == -1意义就是为了特殊边界判断。

三、KMP算法demo

#include <iostream>
#include <string>
#include <vector>
using namespace std;

//部分匹配表
void cal_next(string &str, vector<int> &next)
{
    const int len = str.size();
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < len - 1)
    {
        if (k == -1 || str[j] == str[k])
        {
            ++k;
            ++j;
            next[j] = k;//表示第j个字符有k个匹配(“最大长度值” 整体向右移动一位,然后初始值赋为-1)
        }
        else
            k = next[k];//往前回溯
    }
}

vector<int> KMP(string &str1, string &str2, vector<int> &next)
{
    vector<int> vec;
    cal_next(str2, next);
    int i = 0;//i是str1的下标
    int j = 0;//j是str2的下标
    int str1_size = str1.size();
    int str2_size = str2.size();
    while (i < str1_size && j < str2_size)
    {
        //如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),
        //都令i++,j++. 注意:这里判断顺序不能调换!
        if (j == -1 || str1[i] == str2[j])
        {
            ++i;
            ++j;
        }
        else
            j = next[j];//当前字符匹配失败,直接从str[j]开始比较,i的位置不变
        if (j == str2_size)//匹配成功
        {
            vec.push_back(i - j);//记录下完全匹配最开始的位置
            j = -1;//重置
        }
    }
    return vec;
}

int main(int argc, char const *argv[])
{
    vector<int> vec(20, 0);
    vector<int> vec_test;
    string str1 = "bacbababadababacambabacaddababacasdsd";
    string str2 = "ababaca";
    vec_test = KMP(str1, str2, vec);
    for (const auto v : vec_test)
        cout << v << endl;
    return 0;
}

  KMP时间复杂度:O(m+n)。

四、KMP算法的应用

1、求其中出现重复的任意一个字符

  先求next数组,next[j]=k,k > 0 时,就返回j,p[j]就是出现重复的字符。

这里写图片描述

2、求最长的重复子串

  求最长的重复子串,就是求next[j]=k,求出k的最大值。

这里写图片描述

转自:https://segmentfault.com/a/1190000008575379
https://blog.csdn.net/willinux20130812/article/details/47133425

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/171707.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ItemDataBound的用法

    ItemDataBound的用法原理:在生成datalist列时ItemDataBound触发,也就是说每生成一列就触发一次。这个事件的触发要早于itemcommand.  datalist里面嵌套datalist:内层控件数据绑定与事件声明在外层的ItemDataBind中实现private void dlFileType_ItemDataBound(object sender, System.Web.UI….

    2022年10月13日
  • ES6 数组方法

    ES6 数组方法数组Array为了补充原始数组中某些方法的一些缺陷,ES6在数组方面新增许多API如Array.fromincludefill等等。Array.from()该API可以用来转换类数组与可便利对象将其转化为数组,比如function中的arguments对象(类数组),setmapes6新增的可遍历对象functiontest(){vararr=Array.from(arguments);console.log(arr);}test(1

  • phpstorm激活码2021.12.13【2021最新】

    (phpstorm激活码2021.12.13)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/ide…

  • 通过pycharm使用git和github的步骤(图文详解)[通俗易懂]

    通过pycharm使用git和github的步骤(图文详解)[通俗易懂]目录:导读一、在Pycharm工具中配置集成Git和GitHub。二、推送项目到版本库三、从版本库克隆项目四、通过文件名颜色识别文件状态。五、如何向Git和GitHub仓库中添加文件?六、如何修改Git仓库中的文件?七、如何删除Git仓库中的文件?八、创建分支九、总结一、在Pycharm工具中配置集成Git和GitHub。1.集成Git。打开Pycharm,点击File–>Settins–>VersionControl–>Git.

  • elementui更改el-table表头背景颜色和字体颜色

    elementui更改el-table表头背景颜色和字体颜色博主在使用elementui中的el-table时感觉默认表格样式实在过于简洁,尤其表头与表格内容之间区别较小,不利于辨认,降低了用户体验。如图所示:于是,博主尝试更改一下表头的背景颜色和字体颜色,方法如下:根据elementui官网的说法,header-cell-style是表头单元格的style的回调方法,也可以使用一个固定的Object为所有表头单元格设置一样的Style。…

  • webstorm2021 永久激活码(JetBrains全家桶)

    (webstorm2021 永久激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~2JTX0APX6F-eyJsaWNlb…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号