【第十天】零基础入门刷题Python-算法篇-数据结构与算法的介绍-两种常见的字符串算法(持续更新)

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、Python数据结构与算法的详细介绍
    • 1.Python中的常用的字符串算法
      • 2.字符串算法
      • 3.详细的字符串算法
        • 1)KMP算法
        • 2)Rabin-Karp算法
  • 总结


前言

提示:这里可以添加本文要记录的大概内容:

第一天Python数据结构与算法的详细介绍
第二天五种常见的排序算法
第三天两种常见的搜索算法
第四天两种常见的递归算法
第五天一种常见的动态规划算法
第六天一种常见的贪心算法
第七天一种常见的分治算法
第八天一种常见的回溯算法
第九天六种常见的图论算法
第十天两种常见的字符串算法

提示:以下是本篇文章正文内容,下面案例可供参考

一、Python数据结构与算法的详细介绍

1.Python中的常用的字符串算法

以下是Python中的一些常用算法:

2.字符串算法

字符串算法

  • KMP算法:用于字符串匹配,时间复杂度O(n+m),其中n和m分别是文本和模式的长度。空间复杂度O(m)。
  • Rabin-Karp算法:基于哈希的字符串匹配算法,时间复杂度平均O(n+m),最坏O(n*m)。空间复杂度O(1)(不考虑哈希表)。

3.详细的字符串算法

1)KMP算法
def compute_lps_array(pattern):"""计算部分匹配表(也称为最长前缀后缀数组或失败函数)"""length = 0  # 长度前缀后缀的公共元素lps = [0] * len(pattern)  # 创建lps数组并初始化为0i = 1# 计算lps[i]直到i等于pattern的长度while i < len(pattern):if pattern[i] == pattern[length]:length += 1lps[i] = lengthi += 1else:# (length != 0)意味着我们之前找到了一个前缀后缀# 所以我们不能将长度设为0,因为我们可以通过减少长度来得到一个更小的前缀后缀if length != 0:length = lps[length - 1]# 如果pattern[i] != pattern[length],则我们不需要比较lps[i]# 我们只需要将i增加1else:lps[i] = 0i += 1return lpsdef kmp_search(text, pattern):"""KMP字符串搜索算法"""M = len(pattern)N = len(text)# 创建lps[]数组,它包含pattern的最长前缀后缀值lps = compute_lps_array(pattern)i = 0  # index for textj = 0  # index for patternwhile i < N:if pattern[j] == text[i]:i += 1j += 1if j == M:# 找到匹配项print(f"Found pattern at index {i - j}")j = lps[j - 1]# 当text[i] != pattern[j]时elif i < N and pattern[j] != text[i]:# 不要比较lps[0..lps[j-1]],因为它们不会产生匹配if j != 0:j = lps[j - 1]else:i += 1# 示例用法
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)
2)Rabin-Karp算法
def rabin_karp_search(text, pattern, q=101):"""Rabin-Karp字符串搜索算法"""M = len(pattern)N = len(text)d = 256  # 假设字符集大小(对于ASCII字符)p = 0  # 模式字符串的哈希值t = 0  # 文本字符串的哈希值(初始子串)h = 1# 计算h = d^(M-1) % qfor _ in range(M - 1):h = (h * d) % q# 计算模式和文本第一个子串的哈希值for i in range(M):p = (d * p + ord(pattern[i])) % qt = (d * t + ord(text[i])) % q# 滑动窗口在文本上搜索for i in range(N - M + 1):# 检查哈希值是否匹配if p == t:# 检查实际字符串是否匹配for j in range(M):if text[i + j] != pattern[j]:breakelse:# 找到匹配项print(f"Found pattern at index {i}")# 计算下一个窗口的哈希值if i < N - M:t = (d * (t - ord(text[i]) * h) + ord(text[i + M])) % q# 处理负哈希值(当text[i] * h大于t时)if t < 0:t += q# 示例用法
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
rabin_karp_search(text, pattern)

总结

提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文简单介绍两种常见的字符串算法。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

无耳科技 Solon v3.0.7 发布(2025农历新年版)

Solon 框架&#xff01; Solon 框架由杭州无耳科技有限公司&#xff08;下属 Noear 团队&#xff09;开发并开源。是新一代&#xff0c;面向全场景的 Java 企业级应用开发框架。从零开始构建&#xff08;非 java-ee 架构&#xff09;&#xff0c;有灵活的接口规范与开放生态。…

Redis常用命令合集【一】

1.Redis常用命令 Redis是典型的key-value数据库&#xff0c;key一般是字符串&#xff0c;而value包含很多不同的数据类型&#xff1a; Redis为了方便我们学习&#xff0c;将操作不同数据类型的命令也做了分组&#xff0c;在官网&#xff08; https://redis.io/commands &#…

python学opencv|读取图像(四十八)使用cv2.bitwise_xor()函数实现图像按位异或运算

【0】基础定义 按位与运算&#xff1a;两个等长度二进制数上下对齐&#xff0c;全1取1&#xff0c;其余取0。 按位或运算&#xff1a;两个等长度二进制数上下对齐&#xff0c;有1取1&#xff0c;其余取0。 按位取反运算&#xff1a;一个二进制数&#xff0c;0变1,1变0。 按…

docker 学习笔记

一、docker容器快速上手以及简单操作 docker的image和container image镜像 docker image就是一个read.only文件&#xff0c;可以理解成一个模版&#xff0c;docker image具有分层的概念 可以自己制作&#xff0c;也可以从registry拉去 container容器 一个运行中的docker …

【PyTorch】5.张量索引操作

目录 1. 简单行、列索引 2. 列表索引 3. 范围索引 4. 布尔索引 5. 多维索引 个人主页&#xff1a;Icomi 在深度学习蓬勃发展的当下&#xff0c;PyTorch 是不可或缺的工具。它作为强大的深度学习框架&#xff0c;为构建和训练神经网络提供了高效且灵活的平台。神经网络作为…

穿心莲内酯(andrographolide)生物合成CYP72-文献精读106

Two CYP72 enzymes function as Ent-labdane hydroxylases in the biosynthesis of andrographolide in Andrographis paniculata 两种CYP72酶在穿心莲&#xff08;Andrographis paniculata&#xff09;中作为Ent-labdane羟化酶&#xff0c;在穿心莲内酯&#xff08;andrograp…

关于圆周率的新认知 - 2

当未知长度的单位 1 和已完成长度的单位 1 之间的比例不是 1:1 而是其它的数值的时候&#xff0c;不难看出&#xff0c;这时候的圆周率就变成了“椭圆周率”。你可能要说&#xff0c;这不是椭圆积分吗&#xff1f;对了&#xff0c;这就是椭圆积分。但是我们不要考虑什么椭圆积分…

ARM64平台Flutter环境搭建

ARM64平台Flutter环境搭建 Flutter简介问题背景搭建步骤1. 安装ARM64 Android Studio2. 安装Oracle的JDK3. 安装 Dart和 Flutter 开发插件4. 安装 Android SDK5. 安装 Flutter SDK6. 同意 Android 条款7. 运行 Flutter 示例项目8. 修正 aapt2 报错9. 修正 CMake 报错10. 修正 N…

进程池的制作(linux进程间通信,匿名管道... ...)

目录 一、进程间通信的理解 1.为什么进程间要通信 2.如何进行通信 二、匿名管道 1.管道的理解 2.匿名管道的使用 3.管道的五种特性 4.管道的四种通信情况 5.管道缓冲区容量 三、进程池 1.进程池的理解 2.进程池的制作 四、源码 1.ProcessPool.hpp 2.Task.hpp 3…

新年祝词(原创)

新年将至&#xff0c;福进万户。 家家团圆&#xff0c;事事顺心。 喜迎财神&#xff0c;多寿添金。 瑞兽迎春&#xff0c;炮竹声起。 趋吉避凶&#xff0c;蛇年大吉。 中华崛起&#xff0c;人人自强。 天下大同&#xff0c;百姓富足。 有情有义&#xff0c;平易近人。 …

stack 和 queue容器的介绍和使用

1.stack的介绍 1.1stack容器的介绍 stack容器的基本特征和功能我们在数据结构篇就已经详细介绍了&#xff0c;还不了解的uu&#xff0c; 可以移步去看这篇博客哟&#xff1a; 数据结构-栈数据结构-队列 简单回顾一下&#xff0c;重要的概念其实就是后进先出&#xff0c;栈在…

python:洛伦兹变换

洛伦兹变换&#xff08;Lorentz transformations&#xff09;是相对论中的一个重要概念&#xff0c;特别是在讨论时空的变换时非常重要。在四维时空的背景下&#xff0c;洛伦兹变换描述了在不同惯性参考系之间如何变换时间和空间坐标。在狭义相对论中&#xff0c;洛伦兹变换通常…

DIY QMK量子键盘

最近放假了&#xff0c;趁这个空余在做一个分支项目&#xff0c;一款机械键盘&#xff0c;量子键盘取自固件名称QMK&#xff08;Quantum Mechanical Keyboard&#xff09;。 键盘作为计算机或其他电子设备的重要输入设备之一&#xff0c;通过将按键的物理动作转换为数字信号&am…

【Unity3D】aab包太大无法上传Google问题

目录 一、勾选Split Application Binary&#xff0c;Unity直接打aab包 勾选Split Application Binary选项的影响 不勾选Split Application Binary选项的影响 总结 2、导出Android工程打包aab 一、勾选Split Application Binary&#xff0c;Unity直接打aab包 超出150MB部分…

DeepSeek助力学术文献搜索!

搜集文献 宝子们如果是第一次发表学术论文&#xff0c;论文往往是会署名多个作者。在这种情况下&#xff0c;即便成功发表了论文&#xff0c;独立撰作或主导写作的挑战仍旧存在。那么&#xff0c;怎样才能独立地完成一篇属于自己的学术论文呢&#xff1f;对于初次尝试学术论文…

【时时三省】(C语言基础)文件的随机读写

山不在高&#xff0c;有仙则名。水不在深&#xff0c;有龙则灵。 ----CSDN 时时三省 fseek 根据文件指针的位置和偏移量来定位文件指针 示例&#xff1a; 这个输出的就是ade seek&#xff3f;cur的意思是从当前偏移量 2就是从a往后偏移两个就是d 偏移量 SEEK&#xff3f;CUR…

Python-基于PyQt5,json和playsound的通用闹钟

前言&#xff1a;刚刚结束2024年秋季学期的学习&#xff0c;接下来我们继续来学习PyQt5。由于之前我们已经学习了PyQt5以及PyUIC,Pyrcc和QtDesigner的安装&#xff0c;配置。所以接下来我们一起深入PyQt5&#xff0c;学习如何利用PyQt5进行实际开发-基于PyQt5&#xff0c;json和…

数据结构课程设计(三)构建决策树

3 决策树 3.1 需求规格说明 【问题描述】 ID3算法是一种贪心算法&#xff0c;用来构造决策树。ID3算法起源于概念学习系统&#xff08;CLS&#xff09;&#xff0c;以信息熵的下降速度为选取测试属性的标准&#xff0c;即在每个节点选取还尚未被用来划分的具有最高信息增益的…

2024收尾工作

目录 开场白 栈与队列 LeetCode232. 用栈实现队列 LeetCode225. 用队列实现栈 LeetCode102. 二叉树的层序遍历 LeetCode103. 二叉树的锯齿形层序遍历 堆&#xff08;优先级队列&#xff09; 堆排序 LeetCode215. 数组中的第 k 个最大元素 总结 开场白 今天是除夕&…

纯css实现div宽度可调整

<!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>纯css实现div尺寸可调整</title><style…