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

[python刷题模板] 前缀函数/next数组/kmp算法

[python刷题模板] 前缀函数/next数组/kmp算法

    • 一、 算法&数据结构
      • 1. 描述
      • 2. 复杂度分析
      • 3. 常见应用
      • 4. 常用优化
    • 二、 模板代码
      • 1. 裸前缀函数
      • 2. 树上kmp
      • 3. 裸kmp
    • 三、其他
    • 四、更多例题
    • 五、参考链接

一、 算法&数据结构

1. 描述

前缀函数和next数组基本上是一个东西,但储存的内容不同。
他们是kmp算法的基础。但真的不太好理解,以及不好写,背不过。
前缀函数π(i)可以在O(n)的时间计算出来数组内每个前缀的前缀函数。
  • 参考 oiwiki前缀函数与 KMP 算法
  • kmp还可以结合字典树搞ac自动机,待施工。
  • 前缀函数π[i]代表的前缀s[:i+1]和后缀s[-i:]相同的情况下,是前缀长度。
    • 简单来说 pi[i] 就是,子串 s[0… i] 最长的相等的真前缀与真后缀的长度。
  • next数组是指模式串在i位置匹配失败后,应该向前跳到哪个位置开始继续匹配。

2. 复杂度分析

  1. 预处理O(n)
  2. 查询O(n)

3. 常见应用

  1. 字符串查询。

4. 常用优化

  1. 从意义上来说,前缀函数值得是前后缀相同的长度;next数组是匹配失败后模式串指针j要去的位置。
  • 因此kmp搜索用next数组写法简单点(参考模板代码3);但找前后缀用前缀函数更直观(模板代码1)。

二、 模板代码

1. 裸前缀函数

例题: 4808. 构造字符串
这题暴力能过,但还是前缀函数nb。

# Problem: 构造字符串
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4811/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, infif sys.version >= '3.8':  # ACW没有combfrom math import combRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')MOD = 10 ** 9 + 7def prefix_function(s):"""计算s的前缀函数"""n = len(s)pi = [0] * nfor i in range(1, n):j = pi[i - 1]while j > 0 and s[i] != s[j]:j = pi[j - 1]if s[i] == s[j]:j += 1pi[i] = jreturn pi
#       ms
def solve():n, k = RI()t, = RS()mx = prefix_function(t)[-1]if mx == 0:return print(t * k)suf = t[mx:]print(t + suf * (k - 1))if __name__ == '__main__':solve()

2. 树上kmp

链接: 1367. 二叉树中的链表

试了下树上kmp是负优化,但可能是数据问题。

class Solution:def isSubPath(self, head: ListNode, root: TreeNode) -> bool:path = []while head:path.append(head.val)head = head.nextn = len(path)def get_next(p):n = len(p)nxt = [0]*nnxt[0] = -1j,k=0,-1while j < n-1:if k == -1 or p[j] == p[k]:j+=1k+=1if p[j] == p[k]:nxt[j] = nxt[k]else:nxt[j] = k else:k = nxt[k]return nxtnxt = get_next(path)# print(nxt)def dfs_kmp(tree, j):if j == n:return Trueif not tree:return Falseif j == -1 or tree.val == path[j]:return dfs_kmp(tree.left,j+1) or dfs_kmp(tree.right,j+1)else:return dfs_kmp(tree,nxt[j]) 

3. 裸kmp

链接: 28. 找出字符串中第一个匹配项的下标

class Solution:def strStr(self, haystack: str, needle: str) -> int:m,n = len(haystack),len(needle)# def get_next(p):#     n = len(p)#     nxt = [-1] * n#     j, k = 0, -1#     while j < n - 1:#         if k == -1 or p[j] == p[k]:#             j += 1#             k += 1#             if p[j] == p[k]:#                 nxt[j] = nxt[k]#             else:#                 nxt[j] = k#         else:#             k = nxt[k]#     return nxt# nxt = get_next(needle)# print(nxt)# i = j = 0        # while i < m and j < n:#     if j == -1 or haystack[i] == needle[j]:#         i += 1#         j += 1#     else:#         j = nxt[j]# if j == n:#     return i - j # return -1def prefix_function(s):"""计算s的前缀函数"""n = len(s)pi = [0] * nfor i in range(1, n):j = pi[i - 1]while j > 0 and s[i] != s[j]:j = pi[j - 1]if s[i] == s[j]:j += 1pi[i] = jreturn pipi = prefix_function(needle)print(pi)i ,j = 0,0        while i < m and j < n:while  j > 0 and haystack[i] != needle[j]:j = pi[j-1]if haystack[i] == needle[j]:               j += 1if j == n:return i - j + 1i += 1return -1

三、其他

四、更多例题

五、参考链接

相关文章:

[python刷题模板] 前缀函数/next数组/kmp算法

[python刷题模板] 前缀函数/next数组/kmp算法 一、 算法&数据结构1. 描述2. 复杂度分析3. 常见应用4. 常用优化二、 模板代码1. 裸前缀函数2. 树上kmp3. 裸kmp三、其他四、更多例题五、参考链接一、 算法&数据结构 1. 描述 前缀函数和next数组基本上是一个东西&#…...

rust 程序设计语言入门(1)

本文是阅读《Rust程序设计语言》的学习记录&#xff0c;配合视频《Rust编程语言入门教程》食用更佳 环境搭建 windows下载rustup_init.exe&#xff0c;点击安装&#xff0c;默认选择msvc的toolchain&#xff0c;一路default即可 解决下载慢的问题&#xff0c;在powershell中修…...

基于蜣螂算法改进的LSTM预测算法-附代码

基于蜣螂算法改进的LSTM预测算法 文章目录基于蜣螂算法改进的LSTM预测算法1.数据2.LSTM模型3.基于蜣螂算法优化的LSTM4.测试结果5.Matlab代码摘要&#xff1a;为了提高LSTM数据的预测准确率&#xff0c;对LSTM中的参数利用蜣螂搜索算法进行优化。1.数据 采用正弦信号仿真数据&…...

Python安全开发——Scapy流量监控模块watchdog

目录 Python蓝队项目说明 (一)Python-蓝队项目-Scapy流量分析 0x01 Scapy参数介绍...

阶段二5_集合ArrayList

一.对象数组 1.对象数组使用案例 需求&#xff1a;将&#xff08;张三&#xff0c;23&#xff09;&#xff08;李四&#xff0c;24&#xff09;&#xff08;王五&#xff0c;25&#xff09; 封装为3个学生对象并存入数组 随后遍历数组&#xff0c;将学生信息输出在控制台 思路…...

十一、Python——匿名函数

1.匿名函数:简化函数定义 2.格式 lambda 参数1&#xff0c;参数2…&#xff1a;运算 3.匿名函数特点 不需要指明函数名定义只有一条语句函数体必须是一个表达式不能显示使用return 4.匿名函数实现求和 s lambda a,b:a b result s(1,2) print(result) # 35.匿名函数作…...

数组常使用的方法

1. join (原数组不受影响)该方法可以将数组里的元素,通过指定的分隔符,以字符串的形式连接起来。返回值:返回一个新的字符串const arr[1,3,4,2,5]console.log(arr.join(-)&#xff1b;//1-3-4-2-52. push该方法可以在数组的最后面,添加一个或者多个元素结构: arr.push(值)返回值…...

2023华为软件测试笔试面试真题,抓紧收藏不然就看不到了

一、选择题 1、对计算机软件和硬件资源进行管理和控制的软件是&#xff08;D&#xff09; A.文件管理程序 B.输入输出管理程序 C.命令出来程序 D.操作系统 2、在没有需求文档和产品说明书的情况下只有哪一种测试方法可以进行的&#xff08;A&#xff09; A.错误推测法测…...

洛谷2月普及组(月赛)

&#x1f33c;小宇&#xff08;治愈版&#xff09; - 刘大拿 - 单曲 - 网易云音乐 OI赛制且难度对标蓝桥杯省赛&#xff08;&#x1f625;真难&#xff0c;第三题做了几百年&#xff0c;第四题只敢骗骗分&#xff09; 花了10块钱&#x1f643; 买官网的思路&#xff0c;结果…...

【博学谷学习记录】超强总结,用心分享 | 架构师 Spring源码学习总结

文章目录Spring的循环依赖1.循环依赖的定义&&原因2.循环依赖的场景1.构造器注入引起循环依赖2.Field属性setter注入的循环依赖3.循环依赖解决思路4.三级缓存5.面试题[三级缓存]AOP源码深度剖析概述Spring AOP的前世今生实现机制**JDK 动态代理****CGLIB 代理**流程总结…...

Linux C/C++ timeout命令实现(运行具有时间限制)

Linux附带了大量命令&#xff0c;每个命令都是唯一的&#xff0c;并在特定情况下使用。Linux timeout命令的一个属性是时间限制。可以为任何命令设置时间限制。如果时间到期&#xff0c;命令将停止执行。 如何使用timeout命令 我们将解释如何使用Linux timeout命令 timeout […...

西湖论剑初赛web wp

Node Magical Login 简单的js代码审计。 Flag分成了两部分。 第一部分&#xff1a; 这里就简单的判断了一下user是否等于admin&#xff0c;直接绕过。 第二部分&#xff1a; checkcode ! “aGr5AtSp55dRacer”&#xff0c;让其为真&#xff0c;利用数组绕过。 Flag为&#x…...

【YOLOv8/YOLOv7/YOLOv5系列算法改进NO.55】融入美团最新QARepVGG

文章目录 前言一、解决问题二、基本原理三、​添加方法四、总结前言 作为当前先进的深度学习目标检测算法YOLOv8,已经集合了大量的trick,但是还是有提高和改进的空间,针对具体应用场景下的检测难点,可以不同的改进方法。此后的系列文章,将重点对YOLOv8的如何改进进行详细…...

Flutter Windows端打包并生成可安装文件流程

Windows打包 1.首先安装visual Studio 下载地址&#xff1a;https://visualstudio.microsoft.com/zh-hans/ 下载成功后按照下图勾选桌面应用和移动应用下的使用C的桌面开发&#xff0c;勾选右侧安装详细信息中的windows 11/10 sdk 中的任意一个完成安装即可 2.打包Windows …...

凸优化学习:PART3凸优化问题(持续更新)

凸优化问题 凸优化问题的广义定义&#xff1a; 目标函数为凸函数约束集合为凸集 一、优化问题 基本用语 一般优化问题的描述&#xff1a; minimize⁡f0(x)subject to fi(x)⩽0,i1,⋯,mhi(x)0,i1,⋯,p(1)\begin{array}{ll} \operatorname{minimize} & f_0(x) \\ \text { s…...

[ue4] 着色器绑定(Shader Binding)

当我们在ue4中制作了一个美术材质之后&#xff0c;引擎本身会为我们做很多事情&#xff0c;它会把结点翻译为hlsl&#xff0c;生成多个shader变体&#xff0c;并在多个mesh pass中去选择性的调用所需的shader&#xff0c;其中一个重要的过程就是获取shader绑定的数据。 本文将主…...

Rust语言之迭代器

文章目录Rust迭代器Rust迭代器的实现Iterator特型IntoIterator特型for循环与迭代器迭代器类型再看for循环实现自定义迭代器方式一方式二相关参考Rust迭代器 Rust语言内置了迭代器模式&#xff0c;用于实现对一个项的序列进行特定的处理&#xff0c;通常配合for循环使用。当我们…...

TreeSet 与 TreeMap And HashSet 与 HashMap

目录 Map TreeMap put()方法 : get()方法 : Set> entrySet() (重) : foreach遍历 : Set 哈希表 哈希冲突 : 冲突避免 : 冲突解决 ---- > 比散列(开放地址法) : 开散列 (链地址法 . 开链法) 简介 : 在Java中 , TreeSet 与 TreeMap 利用搜索树实现 Ma…...

Java围棋游戏的设计与实现

技术&#xff1a;Java等摘要&#xff1a;围棋作为一个棋类竞技运动&#xff0c;在民间十分流行&#xff0c;为了熟悉五子棋规则及技巧&#xff0c;以及研究简单的人工智能&#xff0c;决定用Java开发五子棋游戏。主要完成了人机对战和玩家之间联网对战2个功能。网络连接部分为S…...

第七十三章 使用 irisstat 实用程序监控 IRIS - 使用选项运行 irisstat

文章目录第七十三章 使用 irisstat 实用程序监控 IRIS - 使用选项运行 irisstat使用选项运行 irisstatirisstat Options第七十三章 使用 irisstat 实用程序监控 IRIS - 使用选项运行 irisstat 使用选项运行 irisstat 不带选项运行 irisstat 会生成基本报告。通常&#xff0c;…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...