算法通关(3) -- kmp算法

KMP算法的原理

从题目引出

有两个字符串s1和s2,判断s1字符串是否包含s2字符串,如果包含返回s1包含s2的最左开头位置,不包含返回-1,如果是按照暴力的方法去匹配,以s1的每个字符作为开头,用s2的整体去匹配,那么得到的时间复杂度达到O(m*n),若字符串长度过长,那么可能导致不能AC。。。那么可不可以利用前面的匹配过程去帮助匹配加速,某些位置不用按照一个位置一个位置的去匹配。有的,这就是今天要了解的KMP算法。

1.next数组的定义

先知道是怎么回事就行

用s2去匹配s1,next数组是对于s2来说的;含义:不包含当前,它前面字符串前缀和后缀最大匹配长度,也不能包含整体:例如前面的字符串abc,如果包含整体,abc一定匹配abc,没有了意义.

对于0位置的a来说,它的前缀什么都没有,因此放一个-1表示不存在;对于1位置的a来说,前面有一个a,但是只有一个字母,不能够进行匹配,匹配则违反了包含整体(此时整体只有一个1),因此1位置是0;对于2位置b来说,前面是aa,前缀一个a,后缀一个a,刚好匹配,因此填1

对于3位置的a来说,前面是aab,取一个(前缀是a,后缀是b,不行),取两个(前缀是aa,后缀是ab,不行),因此是0.。。。依次类推,对于6位置的x来说,前面是aabaab,最长匹配字符串是3,因此填3

同理:对于12位置的a来说,选择5个是最大的匹配长度。 记住,不包含当前下标的字符!!!

 2.如何加速匹配?

匹配到13位置不相同,下次位置从哪里匹配?匹配不上的next位置是6,那么让s2的6位置的c去匹配s1的13位置,也就是说,前面的1~6位置被放弃了!!!这里引出两个问题:
1:为什么放弃前面的?2:s2的0~5位置为什么不用验证,可以直接从6位置的c开始和s1的13进行匹配?

第二个问题:

先回答第二个问题:因为next数组是不包含当前,它前面字符串前缀和后缀最大匹配长度,为什么是6,因为那个位置的s2字符串前面数6个和后面数6个得到的字符串相同!!!如图:

 由于s1和s2的匹配,可知m1和n1相同,m2和n2相同,又因为next数组,n2和n1相同,那么这四个都相同,就可以得出n1和m2相同,既然相同了,那么就没必要费时间从头开始了。继续匹配如下图:

 第一个问题:

 四个红色方框长度相同.上面说的是s2从k位置开始匹配,假设可以从小于k的位置进行匹配,例如图中的m位置,因为s1的m位置之后和s2之后的字符相同(不包含j位置,因为是从哪里进行的退出),

 从m位置进行匹配可以成功,那么s1的绿色和s2的绿色(下边)一定可以匹配成功,由于s1的绿色第一次匹配时和s2的绿色(上边)匹配成功,因此可以得到s2的这两端绿色是相同的字符串

 而这个长度超过了next数组给定的长度,因为只要匹配上,next算的是不包含当前,它前面字符串前缀和后缀最大匹配长度,违背了next记录最大长度。这样子就加速了匹配的进程

3.KMP算法代码

int kmp(const string& s1, const string& s2) {
    // x是s1的比对位置
    // y是s2的比对位置
    int n = s1.length(), m = s2.length(), x = 0, y = 0;    
    // 获取next数组 
    vector<int> next = nextArray(s2, m);
    // 不越界
    while (x < n && y < m) {
        if (s1[x] == s2[y]) {
            // 每个位置可以匹配的上
            x++;
            y++;
        }
        // 当前不等
        else if (y == 0) {
            // 如果是s2的0位置没有匹配出来,无法往前跳了
            // s1换个位置开头吧,s2不动
            x++;
        }
        else {
            // s2的其他位置没有匹配出来,按照s2的y位置的next[y]跳跃
            // s1不动,s2换个位置配
            y = next[y];
        }
    }
    // s2匹配ok了,就找到了
    // 越界还没有找的,返回-1
    return y == m ? x - y : -1;
}

4.next数组如何快速生成

按照前面的next值求下一个位置的next值

情况1:不用跳

求得“?”位置的next值,看的是前面字符的最大匹配长度,得知是8;也可以看前面“x”位置的next值,是7,看他与7位置的字符是否相同,这里相同,因为不相同就必须跳了,那就+1,得到8,为什么不能够更长呢?如图:

 情况2:需要跳

用图来说吧

 如果没有对上,继续跳,如果跳到头都没有跳出来,那么要求的next就是0。

为什么这样子,其实找的前缀和后缀都是在s2这个字符串中,即在一个字符串中找到尽可能的长的前缀和后缀,这就是next数组的含义,因为要保留尽量长!!!举个例子

 5:next数组代码

vector<int> nextArray(const string& s, int m) {
    // m是字符串s2的长度
    if (m == 1) {
        return { -1 };
    }
    // next的第一个位置和第二个位置是固定的
    vector<int> next(m);
    next[0] = -1;
    next[1] = 0;
    // 从第二个位置开始填
    int i = 2, cn = 0;
    // 没有越界
    while (i < m) {
        // i 表示当前要求的next值的位置
        // cn表示当前要和一个字符比对的下标
        if (s[i - 1] == s[cn]) {
            // 后面的字符是cn位置
            // 为什么是++cn,而不是cn+1
            // 因为为了下面可能用到cn的值,如果后面的字符是cn位置,那么直接用
            // 当前位置求完了,求下一个位置就是++
            next[i++] = ++cn;
        }
        else if (cn > 0) {
            // 不一样,向前跳
            cn = next[cn];
        }
        else {
            // 已经等于0了,再往前跳到-1位置
            next[i++] = 0;
        }
    }
    // 得到next数组
    return next;
}

KMP算法相关题目

题目1:

P4391 [BOI2009] Radio Transmission 无线传输 - 洛谷 | 计算机科学教育新生态

总长度是k个最短长度(设为n)的字串加上尾巴的一些,尾巴长度为L,那么总长度为k*n+L,前缀最大的长度串是(k-1)*n+L,因为此例中是以a开头,下一个a是经过了一次循环后的a,因此可以得到最大长度串。

两个疑惑:它可以更短吗?不可以,因为next求得就是它前面字符串前缀和后缀最大匹配长度
它可以更长吗?不可以,举个例子:
 

正常的情况

出现矛盾!!!

因此可以得出结论:不能够变得更短,也不能变得更长!!!

代码如下:

#include <iostream>
#include <vector>
#include <string>

using namespace std;
const int MAXN = 1000001;
int next_[MAXN];
int n;
string s;

void nextArray() {
    next_[0] = -1;
    next_[1] = 0;
    int i = 2, cn = 0;
    while (i <= n) {
        if (s[i - 1] == s[cn]) {
            next_[i++] = ++cn;
        }
        else if (cn > 0) {
            cn = next_[cn];
        }
        else {
            next_[i++] = 0;
        }
    }
}

int compute() {
    nextArray();
    return n - next_[n];
}

int main() {
    cin >> n;
    cin >> s;
    cout << compute() << endl;
    return 0;
}

题目2:

[USACO15FEB] Censoring S - 洛谷

利用栈,压入s1位置字符的下标以及s2位置字符的下标
如果位置字符下标的值对应,那么两个字符向前++,当s2越界了,那么表示s1的一段和s2匹配上了,那么使栈的长度-s2的长度,然后根据栈顶元素的下标,让s2找到正确的下标。如图:

 代码如下:

#include <iostream>
#include <vector>
#include <string>

using namespace std;


const int MAXN = 1000001;
int next_[MAXN];
// 栈1压s1,栈2压s2
int stack1[MAXN];
int stack2[MAXN];
int _size;
string s1, s2;

// 生成s2的next数组
void nextArray(int m) {
    next_[0] = -1;
    next_[1] = 0;
    int i = 2, cn = 0;
    while (i < m) {
        if (s2[i - 1] == s2[cn]) {
            next_[i++] = ++cn;
        }
        else if (cn > 0) {
            cn = next_[cn];
        }
        else {
            next_[i++] = 0;
        }
    }
}

void compute() {
    _size = 0;
    int n = s1.length(), m = s2.length(), x = 0, y = 0;
    // s2的next数组
    nextArray(m);
    while (x < n) {
        if (s1[x] == s2[y]) {
            // 对应的上,s1和s2两者++
            stack1[_size] = x;
            stack2[_size] = y;
            _size++;
            x++;
            y++;
        }
        // 对应不上,而且y来到s2的开头位置
        else if (y == 0) {
            // 
            stack1[_size] = x;
            stack2[_size] = -1;
            _size++;
            x++;
        }
        // 对应不上,没来到开头位置,往前跳
        else {
            y = next_[y];
        }
        // s2遍历完了
        if (y == m) {
            // 相当于栈直接弹出了m条记录
            _size -= m;
            // 处理s2的y
            // 栈中有东西,跳到栈顶的下一个位置
            // 没有就是0下标
            y = _size > 0 ? (stack2[_size - 1] + 1) : 0;
        }
    }
}


int main() {
    cin >> s1 >> s2;
    compute();
    for (int i = 0; i < _size; i++) {
        cout << s1[stack1[i]];
    }
    cout << endl;
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/910305.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue3+vite搭建脚手架项目使用eletron打包成桌面应用+可以热更新

当前Node版本&#xff1a;18.12.0&#xff0c;npm版本&#xff1a;8.19.2 1.搭建脚手架项目 搭建Vue3ViteTs脚手架-CSDN博客 可删掉index.html文件的title标签 2.配置package.json {"name": "my-vite-project","private": true,"versi…

Java学习者的福音:SpringBoot教学辅助平台

1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理教学辅助平台的相关信息成为必然。开发合适…

JAVA基础:数组 (习题笔记)

一&#xff0c;编码题 1&#xff0c;数组查找操作&#xff1a;定义一个长度为10 的一维字符串数组&#xff0c;在每一个元素存放一个单词&#xff1b;然后运行时从命令行输入一个单词&#xff0c;程序判断数组是否包含有这个单词&#xff0c;包含这个单词就打印出“Yes”&…

网络层5——IPV6

目录 一、IPv6 vs IPv4 1、对IPv6主要变化 2、IPv4 vs IPv6 二、IPv6基本首部 1、版本——4位 2、通信量类——8位 3、流标号——20位 4、有效载荷长度——16位 5、下一个首部——8位 6、跳数限制——8位 7、源 、 目的地址——128位 8、扩展首部 三、IPv6地址 1…

AIRIS 是一种学习型人工智能,它正在自学如何玩 Minecraft

AI开发公司SingularityNET和人工超级智能联盟&#xff08;ASI Alliance&#xff09;表示,随着人工智能学习如何通过操作玩游戏,一种新的学习型AI已被留在Minecraft的实例中。名为AIRIS&#xff08;自主智能增强推断象征主义&#xff09;的AI基本上是从Minecraft内部开始学习如何…

嵌入式学习-网络高级-Day01

嵌入式学习-网络高级-Day01 【1】Modbus协议 起源 分类 优势 应用场景 【2】Modbus TCP 特点 组成 报文头&#xff1a;7个字节 寄存器&#xff08;存储数据&#xff09; 功能码 总结 练习 【3】工具安装 Modbus Slave、Poll安装 网络调试助手 wireshark 练习 【1】Modbus协议 起…

Java项目实战II基于Spring Boot的问卷调查系统的设计与实现(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导 一、前言 在当今信息爆炸的时代&#xff0c;问卷调查…

【c++语言程序设计】数组(对象数组)

数组是一种按照特定顺序排列的对象集合体&#xff0c;数组中的每个对象称为“元素”。数组的每个元素都用“数组名下标”的形式来表示&#xff0c;并且同一数组内的所有元素类型相同。数组可以由任何类型的数据构成&#xff08;除 void 外&#xff09;&#xff0c;且数组的概念…

5分钟跑起来:Java构建的AI人工智能智能问答系统_springboot_spring ai_LLM_人工智能_开源免费使用

Agenda&#xff1a; 1&#xff09;介绍一下AI支持下的智能问答系统有哪些主要模块 2&#xff09;一个可以跑起来的代码样例&#xff0c;说明怎么用Java构建这个AI智能问答系统 AI人工智能智能问答系统简介 智能问答系统是一种利用人工智能技术理解并回答用户提问的应用。该系…

如何基于pdf2image实现pdf批量转换为图片

最近为了将pdf报告解析成为文本和图片&#xff0c;需要将大量多页的pdf文件拆分下单独的一页一页的图像&#xff0c;以便后续进行OCR和图像处理&#xff0c;因此就需要实现将pdf2image&#xff0c;本文主要结合开源的pdf2image和poppler&#xff0c;实现了pdf转换为png格式图片…

Pytorch用BERT对CoLA、新闻组文本数据集自然语言处理NLP:主题分类建模微调可视化分析

原文链接&#xff1a;https://tecdat.cn/?p38181 原文出处&#xff1a;拓端数据部落公众号 自然语言处理&#xff08;NLP&#xff09;领域在近年来发展迅猛&#xff0c;尤其是预训练模型的出现带来了重大变革。其中&#xff0c;BERT 模型凭借其卓越性能备受瞩目。然而&#…

Kaggle:免费 GPU 使用指南,Colab 的理想替代方案

如果电脑显卡性能不足&#xff0c;又无法访问 Colab 的免费 GPU&#xff0c;那该怎么开始之后的学习呢&#xff1f; 答案是 Kaggle。 Kaggle 不仅提供免费的 GPU 计算资源&#xff0c;还可以直连而无需翻墙&#xff0c;同时不需要海外手机号验证。接下来&#xff0c;文章将详细…

Zookeeper 简介 | 特点 | 数据存储

1、简介 zk就是一个分布式文件系统&#xff0c;不过存储数据的量极小。 1. zookeeper是一个为分布式应用程序提供的一个分布式开源协调服务框架。是Google的Chubby的一个开源实现&#xff0c;是Hadoop和Hbase的重要组件。主要用于解决分布式集群中应用系统的一致性问题。 2. 提…

神经网络基础--什么是神经网络?? 常用激活函数是什么???

前言 本专栏更新神经网络的一些基础知识&#xff1b;案例代码基于pytorch&#xff1b;欢迎收藏 关注&#xff0c; 本人将会持续更新。 神经网络 1、什么是神经网络 人工神经网络&#xff08; Artificial Neural Network&#xff0c; 简写为ANN&#xff09;也简称为神经网络…

大模型也要“私人定制“?最新综述带你解锁AI的个性化服务 | 综述!扩散模型:AI艺术创作背后的“魔法引擎“

大模型领域的发展日新月异&#xff0c;每天都有许多有趣的论文值得深入品读。下面是本期觉得比较有意思的论文&#xff1a; 1、大模型也要"私人定制"&#xff1f;最新综述带你解锁AI的个性化服务 2、综述&#xff01;扩散模型&#xff1a;AI艺术创作背后的"魔法…

【MySQL 保姆级教学】深层理解索引及其特性(重点)--上(11)

MySQL与磁盘 1. MySQL与内存和磁盘的联系2. 认识磁盘2.1 MySQL与存储2.2 磁盘结构2.3 扇区2.4 定位扇区 3. MySQL与磁盘交互基本单位4. 建立共识5. 索引的理解5.1 建立一个表并查询5.2 为何 I/O 交互要是Page 6. B树 Vs B 树数6.1 不同存储引擎支持的索引结构类型6.2 B树 Vs B树…

1分钟教你利用ai工具免费制作养生视频,自动化批量操作,效率提升10倍!

养生这个是未来比较火爆的一个赛道,很多人越来越注重养生&#xff0c;你会发现抖音各种健身操博主&#xff0c;视频播放数据都很不错。很多人上一秒说的养生&#xff0c;下一秒又熬起了夜。年纪轻轻就喝起了枸杞续命。 有想做视频号带货的家人&#xff0c;其实可以考虑养生赛道…

思通数科纸质档案扫描与识别与档案馆应用场景介绍

在传统档案馆中&#xff0c;纸质文件的处理和管理是一个重要且繁琐的环节&#xff0c;特别是面对庞大的历史资料库。思通数科的AI能力平台提供了一种高效的数字化解决方案&#xff0c;利用OCR技术将纸质档案中的信息自动提取并转化为数字文本&#xff0c;具体过程包括以下几个步…

AutoCAD的Dwg版本代号、R版本参数值以及二次开发时VS、.NET版本关系

Dwg的AC版本代号 出处&#xff1a;https://www.autodesk.com.cn/support/technical/article/caas/sfdcarticles/sfdcarticles/CHS/drawing-version-codes-for-autocad.html 以下是AutoCAD图形的不同版本代号&#xff1a; MC0.0 - DWG Release 1.1 AC1.2 - DWG R1.2 AC1.4 - DW…

微服务day02

教学文档&#xff1a; 黑马教学文档 Docker Docker的安装 镜像和容器 命令解读 常见命令 案例 查看DockerHub&#xff0c;拉取Nginx镜像&#xff0c;创建并运行容器 搜索Nginx镜像&#xff1a;在 www.hub.docker.com 网站进行查询 拉取镜像&#xff1a; docker pull ngin…