当前位置： 首页 > news >正文

算法·KMP

news 来源：原创 2025/7/6 3:18:09

KMP算法的思想

  • 想要一次性遍历模板串 s 1 s_1 s1​，不在匹配失败时重新开始遍历子串 s 2 s_2 s2​，实现模板串不回退的效果。

KMP数组的理解

KMP数组有两种定义：一是匹配失败后，子串 s 2 s_2 s2​应该回退的位置，一种是 s 2 s_2 s2​[0, i] 部分公共前后缀的长度。

模板+理解

  • 第一个pos:子串的公共前后缀长度
  • 第二个pos:使用KMP算法时，模板串和子串的公共长度
void solve() {cin >> a >> b;a = '0' + a;b = '0' + b;int lena = a.size() - 1, lenb = b.size() - 1,pos=0;//pos的含义:子串的公共前后缀长度kmp[1] = 0;for (int i = 2; i <= lenb; i++) {while (pos && b[pos + 1] != b[i])pos = kmp[pos];if (b[pos + 1] == b[i])pos++;kmp[i] = pos;}pos = 0;//pos的含义:模板串和子串的公共长度for (int i = 1; i <= lena; i++) {while (pos && a[i] != b[pos + 1])pos = kmp[pos];if (a[i]==b[pos+1])pos++;if (pos == lenb) {cout << i - lenb + 1<<endl;pos = kmp[pos];}}for (int i = 1; i <= lenb; i++) {cout << kmp[i] << " ";}
}





例题

  • P3375 【模板】KMP
  • P4391 [BalticOI 2009] Radio Transmission 无线传输:重复字符串，经典KMP题目。注意到原串蕴含重复的子串，左右两端有多出来的子串，但是找规律发现公共前后缀恰好可以表示多出来的子串。于是答案只需要减去多出来的子串就是重复子串的长度。
	for (int i = 2; i <= lena; i++) {while (pos!=0 && a[pos + 1] != a[i])pos = kmp[pos];if (a[pos + 1] == a[i])pos++;kmp[i] = pos;}cout << lena - kmp[lena];
  • P1470 [USACO2.3] 最长前缀 Longest Prefix：这题数据比较水，数据大概 O ( 4 ∗ 1 0 8 ) O(4*10^8) O(4∗108),竟然不卡，用DP建模为背包问题。DP数组的定义是[0,i]是否可以被物体表示。物体就是P集合。
void solve() {int lenp = 0;while (1) {cin >> p;if (p != ".")P[++lenp] = p;else break;}while (cin >> tmp) {s += tmp;}s = '0' + s;//cout <<"s:"<< s << endl;int lens = s.size();dp[0] = true;for (int i = 1; i <= lens; i++) {for (int j = 1; j <= lenp;j++) {string item = P[j];if (i < item.size())continue;string subs = s.substr(i - item.size()+1, item.size());if (subs== item) {dp[i] = dp[i]||dp[i-item.size()];}}}int idx = 0;for (int i = 1; i <= lens; i++) {if (dp[i])idx = i;}cout << idx ;
}
  • SP7155 CF25E - Test：这题很容易看出来就是找重叠部分，但是需要额外注意两个字符串长度相同，前后拼接方式不同，但公共长度相同的情况。这种情况，会有两个新串，需要分类讨论。

相关文章：

算法·KMP

KMP算法的思想 想要一次性遍历模板串 s 1 s_1 s1​&#xff0c;不在匹配失败时重新开始遍历子串 s 2 s_2 s2​&#xff0c;实现模板串不回退的效果。 KMP数组的理解 KMP数组有两种定义&#xff1a;一是匹配失败后&#xff0c;子串 s 2 s_2 s2​应该回退的位置&#xff0c;一种…...

编程日记 2025/7/6 3:18:09

如何正确地写出单例模式

如何正确地写出单例模式 | Jarks Blog 枚举方式&#xff1a; public class SingletonObject {private SingletonObject() {}/*** 枚举类型是线程安全的&#xff0c;并且只会装载一次*/private enum Singleton {INSTANCE;private final SingletonObject instance;Singleton() {…...

编程日记 2025/6/28 23:46:14

Mac M系列 安装 jadx-gui

安装 Homebrew在终端中执行以下命令&#xff08;需管理员密码&#xff09;&#xff1a; 安装 Homebrew&#xff08;官方源&#xff09; /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"国内用户可用镜像源加速&…...

编程日记 2025/7/6 3:08:34

水滴Android面经及参考答案

目录 static 关键字有什么作用，它修饰的方法可以使用非静态的成员变量吗？ Java 中创建线程有几种方式？ wait 和 sleep 的区别，如何打断 sleep？ Java 垃圾回收的目的是什么，垃圾回收机制是怎样的？ Java 的垃圾回收（GC）机制是如何工作的？ 请解释 Java 内存模型（J…...

编程日记 2025/6/29 0:42:30

《猜拳游戏》

综合案例《猜拳游戏》 需求&#xff1a; 本游戏是一款单机游戏&#xff0c;人机交互 规则&#xff1a; 需要双方出拳&#xff1a;石头、剪刀、布 赢&#xff1a; 石头 → 剪刀剪刀 → 布布 → 石头 平&#xff1a; 两边出拳相等 输&#xff1a; … 实现&#xff1a; 选择对…...

编程日记 2025/6/29 0:14:58

Mysql索引优化

一、索引 1. 主键索引&#xff08;Primary Index&#xff09; 定义 主键索引是一种特殊的唯一索引&#xff0c;用于唯一标识表中的每一行数据。每个表最多有一个主键索引&#xff0c;且索引列不允许为 NULL&#xff0c;自动添加 UNIQUE 和 NOT NULL 约束。 特点&#xff1a;…...

编程日记 2025/6/29 0:36:33

Postgresql与openguass对比

背景介绍 PostgreSQL是世界上最先进的开源关系型数据库&#xff0c;以其强大的功能、稳定性和可扩展性著称。而openGauss是华为公司于2020年6月30日开源的数据库系统&#xff0c;内核基于PostgreSQL 9.2.4版本演进而来。值得注意的是&#xff0c;PostgreSQL 11.3版本拥有290个数…...

编程日记 2025/6/29 0:13:01

线程的概念和控制

自从20世纪60年代提出了进程的概念之后&#xff0c;操作系统一直以进程作为独立运行的基本单位。到了20世纪80年代&#xff0c;人们又提出了比进程更小的、能独立运行的基本单位——线程。提出线程的目的是试图提高系统并发执行的程度&#xff0c;从而进一步提高系统的吞吐量。…...

编程日记 2025/6/28 23:44:26

如何配置activemq，支持使用wss协议连接。

1、到阿里云申请一个证书&#xff0c;通过后下载jks证书。 2、配置activemq&#xff1a; 打开activemq安装目录中“conf/activemq.xml”&#xff0c;增加以下记录&#xff1a; <transportConnectors> <transportConnector name"wss" uri"…...

编程日记 2025/6/29 0:04:36

【言语】刷题3

front&#xff1a;刷题2 题干 超限效应介绍冰桶挑战要避免超限效应 B明星的作用只是病痛挑战的一个因素&#xff0c;把握程度才是重点&#xff0c;不是强化弱化明星作用&#xff0c;排除 A虽没有超限效应&#xff0c;但是唯一的点出“冰桶效应”的选项&#xff0c;“作秀之嫌…...

编程日记 2025/6/29 0:59:49

关于 ast: Babel AST 全类型总览

AST 的每个节点都有一个 type 字段&#xff0c;用来标识它的语法类型。 程序结构节点 type说明示例Program整个程序的根节点整体代码结构BlockStatement大括号代码块 {}if、function、for 等的主体ExpressionStatement表达式语句&#xff08;如 a b;&#xff09;EmptyStatem…...

编程日记 2025/6/28 23:02:39

STM32 内存

根据STM32的存储器映射机制&#xff0c;其32位地址总线可访问4GB逻辑地址空间&#xff08;0x00000000-0xFFFFFFFF&#xff09;&#xff0c;但实际物理地址分配由芯片厂商定义。以下是STM32完整的地址映射结构及关键区域说明&#xff1a; 一、地址空间整体架构 4GB地址空间划分…...

编程日记 2025/6/29 1:24:46

图片的require问题

问题 <template><!--第一种方式--><img :src"require(/assets/${imageName})" style"width:100px;" /><!--第二种方式--><img :src"require(imageUrl)" style"width:100px;" /> </template><…...

编程日记 2025/6/29 0:23:00

关于 js：8. 反调试与混淆识别

一、常见反调试手段识别 1. debugger 死循环&#xff08;阻塞调试器&#xff09; 样例代码&#xff1a; while (true) {debugger; }原理&#xff1a; 每次执行到 debugger 语句&#xff0c;如果 DevTools 打开&#xff0c;将自动触发断点。 如果在死循环中&#xff0c;调试…...

编程日记 2025/7/5 10:20:11

深度Q网络（DQN）的基本概念

一、深度Q网络（DQN）的基本概念 深度Q网络（Deep Q-Network，DQN）是将强化学习中的Q学习（Q-Learning）与深度学习相结合的算法，由DeepMind在2013年提出，并在2015年发表于《Nature》杂志。它通过神经网络近似动作价值函数（Q函数），解决传统Q学习在高维状态空间下的计算难…...

编程日记 2025/6/29 0:00:27

uniapp+vue3中自动导入ref等依赖

前言&#xff1a; 在我们使用uni-appvue3创建项目&#xff0c;开发的过程中&#xff0c;老是需要导入我们的ref、onshow等&#xff0c;那么能不能自动导入&#xff0c;不用我们每个页面都写呢&#xff1f;是没问题的&#xff0c;这里让他的小帮手来帮你减轻负担&#xff1a;他就…...

编程日记 2025/6/29 1:13:53

合肥SMT贴片加工核心优势与工艺升级

内容概要 在电子制造领域&#xff0c;工艺精度与生产效率的平衡始终是企业关注的核心命题。本文将系统呈现合肥SMT贴片加工产业的技术演进图谱&#xff0c;为寻求制造升级的企业提供可落地的决策参考。 作为长三角电子制造集群的重要节点&#xff0c;合肥SMT贴片加工产业通过持…...

编程日记 2025/6/29 0:46:26

Ansible安装与核心模块实战指南

Ansible安装与核心模块实战指南 自动化运维入门：从安装到模块化任务配置 Ansible作为一款无代理自动化工具，通过模块化设计实现高效管理，尤其适用于快速部署、配置和维护大规模系统。本文将从安装、核心模块使用到实际案例，全面解析其核心功能与最佳实践。 一、Ansible安装…...

编程日记 2025/6/29 1:15:24

TDengine 做为 Spark 数据源

简介 Apache Spark 是开源大数据处理引擎&#xff0c;它基于内存计算&#xff0c;可用于批、流处理、机器学习、图计算等多种场景&#xff0c;支持 MapReduce 计算模型及丰富计算操作符、函数等&#xff0c;在大超大规模数据上具有强大的分布式处理计算能力。 通过 TDengine …...

编程日记 2025/6/29 0:15:58

Codeforces Round 997 (Div. 2)

A. Shape Perimeter 题目大意 给你一个m*m的正方形&#xff0c;再给你n个坐标表示每次在xy移动的距离&#xff08;第一个坐标是初始位置正方形左下角&#xff09;&#xff0c;问路径图形的周长 解题思路 记录好第一次的位置之后一直累加最后求总移动距离的差值即可 代码实…...

编程日记 2025/6/28 23:02:41

WSL 安装 Debian 12 后，Linux 如何安装 nginx ?

在 WSL 的 Debian 12 中安装 Nginx 的步骤如下&#xff1a; 1. 更新系统软件包 sudo apt update && sudo apt upgrade -y2. 安装 Nginx sudo apt install nginx -y3. 管理 Nginx 服务 ▶ 启动 Nginx sudo service nginx start # 如果使用 systemd 可能需改用&…...

编程日记 2025/6/29 0:12:24

目标检测任务 - 数据增强

目标检测任务 - DETR &#xff1a; 数据预处理/数据增强 算法源码实例 import datasets.transforms as Tnormalize T.Compose([T.ToTensor(),T.Normalize([0.485, 0.456, 0.406], [0.229, 0.224, 0.225]) ])scales [480, 512, 544, 576, 608, 640, 672, 704, 736, 768, 800]…...

编程日记 2025/7/3 21:13:55

java的switch case

import java.util.Scanner;public class Hello {public static void main(String[] args) {Scanner in new Scanner(System.in);int type in.nextInt();switch(type){case 1:case 2:System.out.println("你好");break;case 3:System.out.println("晚上好"…...

编程日记 2025/6/29 1:18:14

基于亚博K210开发板——LCD触摸屏读取坐标数据测试

开发板 亚博K210开发板 实验目的 主要学习 K210 通过 I2C 读取触摸屏的坐标&#xff0c;并打印出来&#xff0c;显示在 LCD上。 实验准备 实验元件 LCD 显示屏触摸板 元件特性 K210 开发板自带 2.0 寸触摸屏&#xff0c;其实是 LCD 显示屏上贴一个触摸板组成&#xf…...

编程日记 2025/6/29 0:56:59

coze平台实现文生视频和图生视频（阿里云版）工作流

工作流全貌 开始 首先从入参开始&#xff1a; api_key&#xff1a;来自阿里云百炼平台&#xff0c;自行去申请 prompt&#xff1a;生成视频的文本提示词。支持中英文&#xff0c;长度不超过800个字符&#xff0c;每个汉字/字母占一个字符&#xff0c;超过部分会自动截断。 …...

编程日记 2025/6/29 0:21:10

python酒店健身俱乐部管理系统

目录 技术栈介绍具体实现截图系统设计研究方法&#xff1a;设计步骤设计流程核心代码部分展示研究方法详细视频演示试验方案论文大纲源码获取/详细视频演示 技术栈介绍 Django-SpringBoot-php-Node.js-flask 本课题的研究方法和研究步骤基本合理&#xff0c;难度适中&#xf…...

编程日记 2025/6/29 0:43:43

QtGUI模块功能详细说明，图标和光标（七）

目录 一.窗口和屏幕管理 二. 绘图和渲染 三. 图像处理 四. 字体和文本 五. 事件和输入处理 六. OpenGL 和硬件加速 七. 颜色和外观 八. 图标和光标 1、QIcon: 图标管理 1.1、QIcon 简介 1.2、图标的来源与创建 1.3、多分辨率与 DPI 支持 1.4、图标的状态管理 2、…...

编程日记 2025/6/29 0:04:28

【图像处理基石】如何入门OCR技术？

入门OCR&#xff08;Optical Character Recognition&#xff0c;光学字符识别&#xff09;技术需要结合理论学习、工具实践和项目实战&#xff0c;以下是分步骤的学习指南&#xff0c;适合零基础学习者&#xff1a; 一、明确OCR技术的核心概念 OCR的基本原理 核心流程&#xf…...

编程日记 2025/6/29 0:18:28

数据库知识沉浸式游戏化学习设计研究

数据库知识沉浸式游戏化学习设计研究 摘要： 本研究旨在设计一款以数据库知识为主题的沉浸式游戏化学习系统。通过对数据库知识体系的深入剖析，结合游戏化学习理论，构建了一个多层次、多任务的游戏架构。玩家在游戏过程中需完成构建数据库结构、编写 SQL 查询等任务来解锁关…...

编程日记 2025/6/28 23:45:37

大疆无人机

在大疆上云API中&#xff0c;​​DRC 链路​​通常指 ​​Device-Cloud Remote Control Link&#xff08;设备-云端远程控制链路&#xff09;​​&#xff0c;它是无人机&#xff08;或设备&#xff09;与云端服务之间建立的​​实时控制与数据传输通道​​&#xff0c;用于实现…...

编程日记 2025/6/28 23:07:47

撤回不了一点 v1.0.2，支持微信QQ钉钉飞书等消息防撤回

如今生活节奏快得飞起&#xff0c;社交软件和工作通讯软件成了咱日常交流的核心阵地。大家肯定都有过这些闹心事儿&#xff1a;和朋友聊得正嗨&#xff0c;对方突然撤回一条消息&#xff0c;好奇心瞬间爆棚&#xff0c;却怎么也看不到撤回的内容&#xff1b;工作群里关键信息刚…...

编程日记 2025/6/29 1:26:46

什么是Git？

“Git”是目前非常火、广泛使用的版本控制系统&#xff0c;尤其在软件开发领域中扮演着核心角色。 一、什么是Git&#xff1f;它到底是什么&#xff1f; Git 是一种版本控制系统&#xff08;Version Control System, VCS&#xff09;。它的主要作用是帮助开发者管理“代码的不…...

编程日记 2025/6/29 9:00:10

微信小程序 自定义图片分享-绘制数据图片以及信息文字

一 、需求 从数据库中读取头像&#xff0c;姓名电话等信息&#xff0c;当分享给女朋友时&#xff0c;每个信息不一样 二、实现方案 1、先将数据库中需要的头像姓名信息读取出来加载到data 数据项中 data:{firstName:, // 姓名img:, // 头像shareImage:,// 存储临时图片 } 2…...

编程日记 2025/6/29 0:26:18

langchain提示词的使用

一、概述 提示词是指向人工智能大模型提供的输入信息&#xff0c;通常包含关键词、问题或指令&#xff0c;可以引导大模型生成与用户期望相符的回应。我们在豆包&#xff0c;DeepSeek等大模型中输入的问题都可以认为一个简单的提示词&#xff0c;不过为了真正得到我们需要的结…...

编程日记 2025/6/28 23:57:21

C语言| extern的用法作用

C语言| 局部变量、全局变量 extern定义的变量&#xff0c;只对全局变量有用。 掌握extern的用法及其作用。extern主要用于在不同.c文件间扩展全局变量的作用范围。 扩展全局变量的使用范围&#xff0c;操作方法&#xff1a; 1 在一个文件内扩展全局变量的使用范围 全局变量…...

编程日记 2025/6/28 23:08:23

Rust 环境变量管理秘籍：从菜鸟到老鸟都爱的 dotenv 教程

前言 写代码的你，是否遭遇过这些灵魂拷问： “我现在在哪个环境？开发？测试？还是直接在生产线上裸奔？”“少写一个 .env，测试脚本在数据库里上演清空大法，客户当场破防。”“每次手动设置 RUST_ENV，命令敲到一半就开始怀疑人生，还怕输错一个字符引发灭世级事故。”别慌…...

编程日记 2025/6/29 0:43:26

Leetcode （力扣）做题记录 hot100（49，136，169，20）

力扣第49题&#xff1a;字母异位词分组 49. 字母异位词分组 - 力扣&#xff08;LeetCode&#xff09; 遍历数组&#xff0c;将每一个字符串变成char数组 然后排序&#xff0c;如果map里面有则将他的值返回来&#xff08;key是排序好的字符串&#xff09; class Solution {pu…...

编程日记 2025/6/29 0:08:36

Slitaz 系统深度解析

Slitaz 系统深度解析&#xff1a;从系统架构到设计哲学 一、系统定位与核心目标 Slitaz&#xff08;Simplified Lightweight IT Automatic Zen&#xff09;是一个基于 Linux 的超轻量级发行版&#xff0c;设计目标是极致轻量化、快速启动、低资源消耗&#xff0c;专为老旧硬件…...

编程日记 2025/6/28 23:37:04

Deepseek+Xmind：秒速生成思维导图与流程图

deepseekxmind&#xff0c;快速生成思维导图和流程图 文章目录 思维导图deepseek笔记本 txt文件xmind 流程图deepseekdraw.io 思维导图 deepseek 笔记本 txt文件 将deep seek的东西复制到文本文件中&#xff0c;然后将txt文件拓展名改成md xmind 新建思维导图----左上角三…...

编程日记 2025/6/28 23:11:31

理解计算机系统_并发编程(5)_基于线程的并发(二):线程api和基于线程的并发服务器

前言 以<深入理解计算机系统>(以下称“本书”)内容为基础&#xff0c;对程序的整个过程进行梳理。本书内容对整个计算机系统做了系统性导引,每部分内容都是单独的一门课.学习深度根据自己需要来定 引入 接续上一篇理解计算机系统_并发编程(4)_基于线程的并发(一…...

编程日记 2025/6/28 23:12:23

java刷题基础知识

List<int[]> merged new ArrayList<int[]>(); return merged.toArray(new int[merged.size()][]); 表示一个存储 int[] 类型元素的列表&#xff0c;list灵活支持扩展&#xff0c;因为不知道最后有几个区间&#xff0c;所以用list&#xff0c;最后toArray返回成数组…...

编程日记 2025/6/28 23:29:49

MATLAB语音情感识别神经网络方法

在MATLAB中使用神经网络进行语音情感识别通常涉及以下步骤&#xff1a;数据准备、特征提取、神经网络模型构建、训练与评估。以下是详细说明和示例代码&#xff1a; 1. 数据准备 数据集&#xff1a;推荐使用公开情感语音数据集&#xff08;如RAVDESS、CREMA-D、EMODB等&#x…...

编程日记 2025/6/28 23:20:57

PostgreSQL 服务器信号函数

PostgreSQL 服务器信号函数 PostgreSQL 提供了一组服务器信号函数&#xff08;Server Signaling Functions&#xff09;&#xff0c;允许数据库管理员向 PostgreSQL 服务器进程发送特定信号以控制服务器行为。这些函数提供了对数据库服务器的精细控制能力。 一、核心信号函数…...

编程日记 2025/6/29 1:24:06

流动式起重机Q2的培训内容有哪些？

流动式起重机 Q2 的培训内容主要分为理论知识和实际操作两部分&#xff0c;具体如下&#xff1a; 理论知识 基础理论知识&#xff1a;涵盖机械原理、液压原理、电气原理等内容&#xff0c;帮助学员理解起重机的基本工作原理。例如&#xff0c;通过机械原理知识&#xff0c;学员…...

编程日记 2025/7/1 20:50:04

虹科应用 | 探索PCAN卡与医疗机器人的革命性结合

随着医疗技术的不断进步&#xff0c;医疗机器人在提高手术精度、减少感染风险以及提升患者护理质量方面发挥着越来越重要的作用。医疗机器人的精确操作依赖于稳定且高效的数据通信系统&#xff0c;虹科提供的PCAN四通道mini PCIe转CAN FD卡&#xff0c;正是为了满足这一需求而设…...

编程日记 2025/6/29 0:14:39

Linux系统编程---Signal信号集

0、前言 在上一篇博客笔记文章中&#xff0c;对Linux进程间通信的信号进行了讲解&#xff0c;本章将接着上一篇文章的内容&#xff0c;继续对Linux进程间通信中信号部分的信号集这个小知识点进行梳理。 如果有对Linux系统编程有不了解的地方&#xff0c;欢迎查阅博主的Linux系统…...

编程日记 2025/7/5 11:20:29

上电单次复位触发电路

SA1相当于是另外一个触发信号&#xff0c;S2A是手动触发信号&#xff0c;当S1A和S2A开关都断开时,示波器A入口所连接线路为上拉状态&#xff0c;高电平为3V。 当S2A闭合&#xff0c;相当于手动拉低&#xff0c;可以用于唤醒单片机之类的。 当S1A闭合&#xff0c;模拟电源接入&…...

编程日记 2025/6/29 0:00:24

talk-linux 不同用户之间终端通信

好的&#xff01;下面是一个完整的指南和脚本&#xff0c;用于在两台 Linux 主机上配置并使用 talk 聊天功能&#xff08;假设它们在同一个局域网内&#xff09;。 ⸻ &#x1f9fe; 一、需求说明 我们需要在两台主机上&#xff1a; 1. 安装 talk 和 talkd 2. 启用 talkd 服…...

编程日记 2025/7/4 11:56:59

QGIS 将 Shapefile 导入 PostGIS 数据库

一、背景介绍&#xff1a;QGIS、PostgreSQL 和 PostGIS 的关系和用途 在开始动手操作之前&#xff0c;我们先简单了解一下 QGIS、PostgreSQL 和 PostGIS 之间的关系及其用途。 QGIS&#xff08;Quantum GIS&#xff09;&#xff1a;一款开源免费的桌面地理信息系统&#xff0…...

编程日记 2025/6/28 23:02:52

《内网渗透测试：绕过最新防火墙策略》

内网渗透测试是检验企业网络安全防御体系有效性的核心手段&#xff0c;而现代防火墙策略的持续演进&#xff08;如零信任架构、AI流量分析、深度包检测&#xff09;对攻击者提出了更高挑战。本文系统解析2024年新型防火墙的防护机制&#xff0c;聚焦协议隐蔽隧道、上下文感知绕…...

编程日记 2025/6/28 23:42:41