字符串匹配的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)
blank

相关推荐

  • Linux中top命令_linux tail命令详解

    Linux中top命令_linux tail命令详解原标题:Linux下top命令详解1、简介top命令是Linux下常用的性能分析工具,能够实时显示系统中各个进程的资源占用状况,类似于Windows的任务管理器。top显示系统当前的进程和其他状况,是一个动态显示过程,可以自动或者通过用户按键来不断刷新当前状态。如果在前台执行该命令,它将独占前台,直到用户终止该程序为止.。比较准确的说,top命令提供了实时的对系统处理器的状态监控,显示系统中CPU…

  • ActiveMQ之ActiveMQ-CPP安装及测试

    在介绍ActiveMQ-CP之前,先介绍下CMS(C++MessagingService),CMS是C++程序与消息中间件进行通信的一种标准接口,可以通过CMS接口与类似ActiveMQ这样的消息

    2021年12月29日
  • oracle怎样将数据库恢复到某个时间点之前_oracle删除时间段之前的数据

    oracle怎样将数据库恢复到某个时间点之前_oracle删除时间段之前的数据deletefromtablename;insertintotablenameselect*fromtablenameasoftimestampto_timestamp(‘2017-01-0811:00:00′,’yyyy-mm-ddhh24:mi:ss’)注意:1.表结构更改了不可使用此方法恢复数据;2.时间间隔不能太长(几个小时还是没…

  • netty权威指南第二版源码 百度云_dubbo源码视频

    netty权威指南第二版源码 百度云_dubbo源码视频netty权威指南第二版源码 https://github.com/wuyinxian124/nettybook2

  • 计算机病毒模块测试题,计算机病毒分类测试题集

    计算机病毒模块测试题,计算机病毒分类测试题集以下有关计算机病毒分类的陈述______是正确的.A)病毒分为十二类B)病毒分为操作系统类型和文件类型C)没有分类D)病毒分为外壳型和侵入型根据计算机病毒的破坏能力,计算机病毒可分为A.良性病毒B.恶性病毒C.网络病毒D.引导病毒根据计算机病毒的存在方式进行分类,通常可以分为().A.复杂病毒B.引导病毒C.文件病毒D.网络病毒这个问题是一个选择题.请帮助给出正确的答案和分析,谢…

  • 手摸手教你写一个vue的toast弹窗[通俗易懂]

    手摸手教你写一个vue的toast弹窗[通俗易懂]前言:我们在项目开发的过程中,也许会在很多页面实现弹窗的消息,普通的方法就是在这每个界面写些原生js代码来控制弹窗效果,这样明显非常冗余。可通过引入组件的方式,可解决部分冗余的代码,但是每个要使用的界面都必须导入、注册、使用,这些代码还是比较冗余。通过插件的方式封装Toast,可解决每个页面重复导入、注册、使用的重复过程。一.封装Toast组件css自行设计二.Toast插件方式的封装在使用Toast前需要做相应的准备工作:添加一个index.js文件-里面定义一个对象-然后导

发表回复

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

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