KMP匹配算法

news/2024/11/6 15:41:31/

目录

  • 一、暴力匹配法
    • 动画演示
    • 代码实现
  • 二、KMP算法的概念
  • 三、KMP算法的应用
    • 题目
    • 代码实现


一、暴力匹配法

动画演示

暴力遍历法
时间复杂度为: O ( m ∗ n ) O(m * n) O(mn)

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;int find(string& s1, string& s2)
{int n = s1.size();int m = s2.size();for (int i = 0; i <= n - m; ++i){int cp = i, j = 0;while (cp < n && s1[cp] == s2[j]) cp++, j++;if (j == m - 1) return cp;}return -1;
}
int main()
{string txt = "ABCDABCDABDE";string pat = "ABCDABD";cout << find(txt, pat) << endl;return 0;
}

二、KMP算法的概念

K M P KMP KMP 算法,通常用于在一个 文本字符串 S S S 中查找一个 匹配串 P P P出现位置出现次数

KMP算法

KMP算法首先对模式串进行预处理,计算出Next数组。Next数组的每个元素表示当前位置之前的子串中,最长的相等的前缀和后缀的长度。然后,在匹配过程中,使用Next数组来指导模式串的移动。

当模式串与文本串的某个字符不匹配时,根据Next数组的值确定模式串的移动位置,而不是从头开始逐个字符地比较。通过合理地利用Next数组,KMP算法能够有效地避免不必要的比较操作,从而提高匹配的效率。

难点在于通过预处理得到Next数组 及其 回退处理的操作

相关求解视频:

【搬运】油管阿三哥讲KMP查找算法,中英文字幕,人工翻译,简单易懂


三、KMP算法的应用

题目

题目描述:
给定一个字符串 S S S,以及一个模式串 P P P,所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P P P 在字符串 S S S 中多次作为子串出现。

求出模式串 P P P 在字符串 S S S 中所有出现的位置的起始下标。

输入格式:
第一行,输入整数 n n n,表示字符串 P P P 的长度。

第二行,输入字符串 P P P

第三行,输入整数 m m m,表示字符串 S S S 的长度。

第四行,输入字符串 S S S

输出格式:
共一行,输出所有出现位置的起始下标(下标从 0 0 0 开始计数),整数之间用空格隔开。

数据范围:
1 ≤ n ≤ 1 0 5 1≤n≤10^5 1n105
1 ≤ m ≤ 1 0 6 1≤m≤10^6 1m106

输入样例:

3
aba
5
ababa

输出样例:

0 2

代码实现

const int N = 1e5 + 10, M = 1e6 + 10;int ne[N];
char s[M];
char p[N];int main()
{cin.tie(nullptr);int n, m;cin >> n;for (int i = 0; i < n; ++i) cin >> p[i];cin >> m;for (int i = 0; i < m; ++i) cin >> s[i];// 创建Next数组// i:当前试图进行匹配的S串字符,j是模板串当前试图与S串i位置进行匹配的字符// j:表示已匹配的长度,一直都在尝试让j位和i位进行匹配,退无可退,无需再退。// i:是从1开始的,因为ne[0]=0,表示第1个不匹配,只能重头开始,不用算for (int i = 1, j = 0; i < n; i++) // j - 前缀末,i - 后缀末{while (j && p[i] != p[j]) j = ne[j - 1];if (p[i] == p[j]) j++;ne[i] = j;}for (int i = 0, j = 0; i < m; i++){while (j && s[i] != p[j]) j = ne[j - 1];if (s[i] == p[j]) j++;if (j && j == n){printf("%d ", i + 1 - n);j = ne[j - 1];}}return 0;
}

http://www.ppmy.cn/news/68070.html

相关文章

前端架构师-week5-脚手架下载升级项目模版功能开发

目录 脚手架下载项目模版功能开发 通过 spinner 实现命令行 loading 效果 项目模版更新功能调试 脚手架下载项目模版功能开发 当作 npm 模块来处理&#xff0c;尝试对它进行下载。 commands/init/ 的 package.json 中注册 models/package/&#xff0c;并在命令行中执行 npm i…

怎样删除hao123(浏览器首页被篡改了)

有时候我们打开浏览器发现首页被hao123 ,或者2345 这些浏览器给篡改了 或者打开的时候直接打开2个.这个时候想要删除它们,其他它们本身就是网页的,没有应用 在卸载的地方就不用了,它们就嵌套你的浏览器里面,打开的时候启动了他们, 下面说下方法 1 查看浏览器在什么方法下载…

【软考数据库】第十一章 数据库设计

目录 11.1 数据库设计概述 11.2 系统需求分析 11.3 概念结构设计 11.4 逻辑结构设计 11.5 物理结构设计 11.6 实施阶段 11.7 运行与维护 11.7.1 数据库系统的运行 11.7.2 数据库系统的维护 11.7.3 数据库系统的管理 11.7.4 性能调整 前言&#xff1a; 笔记来自《文…

zigbee MQTT控制小米蓝牙插座开和关 型号Xiao Mi zigbee ZNCZ02LM 或支持zigbee的插座或设备

zigbee MQTT控制小米蓝牙插座开和关 型号Xiao Mi zigbee ZNCZ02LM 或支持zigbee的插座或设备 硬件准备 小米蓝牙插座&#xff0c;型号: Xiao Mi zigbee ZNCZ02LM 或支持zigbee的插座或设备 zigbee设备&#xff0c;型号: CC2531设备 参考链接: https://github.com/Koenkk/zi…

Swoole定时器实现毫秒级任务调度

简介 Timer 毫秒精度的定时器&#xff0c;底层基于 epoll_wait 和 setitimer 实现&#xff0c;数据结构使用最小堆&#xff0c;可支持添加大量定时器&#xff0c;使用最小堆数据结构实现的定时器&#xff0c;类似 JavaScript 的 setInterval&#xff0c;Swoole 定时器的添加和…

练习时长两年半的扫雷

目录 设计思路 游戏运行效果 函数的声明 头文件game.h 游戏主体(源文件) 1.game.c 2.test.c 各文件的阐述 各部分设计心得 1.打印菜单 2.初始化雷池 3.打印雷池以及玩家界面 打印效果 如何改变雷的数量与雷池大小 4.生成随机雷 5.排雷与对局判断 对于越界的看法 设计…

VMware、CentOS、XShell、Xftp的安装

第 1 章 VMware 1.1 VMware 安装 一台电脑本身是可以装多个操作系统的&#xff0c;但是做不到多个操作系统切换自如&#xff0c;所以我们 需要一款软件帮助我们达到这个目的&#xff0c;不然数仓项目搭建不起来。 推荐的软件为 VMware&#xff0c;VMware 可以使用户在一台计…

MS5147/MS5148模数转换器可pin对pin兼容ADS1247/ADS1248

‎ADS1246、ADS1247 和 ADS1248 是高度集成的精密 24 位模数转换器 &#xff08;ADC&#xff09;。这些器件具有一个板载、低噪声、可编程增益放大器 &#xff08;PGA&#xff09;、一个带有单周期建立数字滤波器的精密三角积分 &#xff08;ΔΣ&#xff09; ADC 和一个内部振…