当前位置: 首页 > 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;…...

【博客619】PromQL如何实现Left joins以及不同metrics之间的复杂联合查询

PromQL如何实现Left joins以及不同metrics之间的复杂联合查询 1、场景 我们需要在PromQL中实现类似SQL中的连接查询&#xff1a; SELECT a.value*b.value, * FROM a, b2、不同metrics之间的复杂联合查询 瞬时向量与瞬时向量之间进行数学运算&#xff1a; 例如&#xff1a;根…...

Win11自定义电脑右下角时间显示格式

Win11自定义电脑右下角时间显示格式 一、进入附加设置菜单 1、进入控制面板&#xff0c;选择日期和时间 2、选择修改日期和时间 3、选择修改日历设置 4、选择附加设置 二、自定义时间显示出秒 1、在选项卡中&#xff0c;选时间选项卡 2、在Short time的输入框中输入H:m…...

TrueNas篇-trueNas Scale安装

安装TrueNAS Scale 在尝试trueNas core时发下可以成功安装&#xff0c;但是一直无法成功启动&#xff0c;而且国内对我遇见的错误几乎没有案例&#xff0c;所以舍弃掉了&#xff0c;而且trueNas core是基于Linux的&#xff0c;对Linux的生态好了很多&#xff0c;还可以可以在t…...

element表单搜索框与表格高度自适应

一般在后台管理系统中&#xff0c;表单搜索框和表格的搭配是非常常见的&#xff0c;如下所示&#xff1a; 在该图中&#xff0c;搜索框有五个&#xff0c;分为了两行排列。但根据大多数的UI标准&#xff0c;搜索框默认只显示一行&#xff0c;多余的需要进行隐藏。此时的页面被…...

MySQL使用技巧整理

title: MySQL使用技巧整理 date: 2021-04-11 00:00:00 tags: MySQL categories:数据库 重建索引 索引可能因为删除&#xff0c;或者页分裂等原因&#xff0c;导致数据页有空洞&#xff0c;重建索引的过程会创建一个新的索引&#xff0c;把数据按顺序插入&#xff0c;这样页面…...

七大设计原则之里氏替换原则应用

目录1 里氏替换原则2 里氏替换原则应用1 里氏替换原则 里氏替换原则&#xff08;Liskov Substitution Principle,LSP&#xff09;是指如果对每一个类型为 T1 的对象 o1,都有类型为 T2 的对象 o2,使得以 T1 定义的所有程序 P 在所有的对象 o1 都替换成 o2 时&#xff0c;程序 P…...

1行Python代码去除图片水印,网友:一干二净

大家好&#xff0c;这里是程序员晚枫。 最近小明在开淘宝店&#xff08;店名&#xff1a;爱吃火锅的少女&#xff09;&#xff0c;需要给自己的原创图片加水印&#xff0c;于是我上次给她开发了增加水印的功能&#xff1a;图片加水印&#xff0c;保护原创图片&#xff0c;一行…...

Connext DDS属性配置参考大全(2)

DDSSecure安全com.rti.servcom.rti.serv.load_plugin...

一起Talk Android吧(第四百九十二回:精简版动画)

文章目录概念介绍使用方法示例代码经验总结各位看官们大家好&#xff0c;上一回中咱们说的例子是"动画集合&#xff1a;AnimatorSetBuilder",这一回中咱们说的例子是" 精简版动画"。闲话休提&#xff0c;言归正转&#xff0c;让我们一起Talk Android吧&…...

seata源码-全局事务回滚服务端源码

这篇博客来记录在发起全局事务回滚时&#xff0c;服务端接收到netty请求是如何处理的 1. 发起全局事务回滚请求 在前面的博客中&#xff0c;有说到过&#xff0c;事务发起者在发现分支事务执行异常之后&#xff0c;会提交全局事务回滚的请求到netty服务端&#xff0c;这里是发…...