字符串匹配新秀之Sunday

2023-12-03 22:18
文章标签 字符串 匹配 新秀 sunday

本文主要是介绍字符串匹配新秀之Sunday,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Sunday算法的大致思想是,以pos表示本次匹配的目标串tar的起始位置,len_m表示模式串的长度,当出现不匹配的时候,看从pos开始长为len_m的一段字串的最后一个字符k是否在模式串中出现过,判断是否出现过是通过从右到左扫描模式串得到的,只要碰到k,记录下其位置i,将pos+i作为新的pos(pos+=i),继续匹配。这就扯出了next数组,不要将这个next数组跟KMP中的数组牵连起来,二者没任何关系。next数组就是记录模式串中的字母离串尾的距离,若某个字符重复出现,则只记录最右边的那个,next初始值是模式串的长度,即如果某个字符没在mode串中出现,那么pos移动时就是整体平移一个模式串的距离。next[i]表示字母i距离模式串末尾的距离,pos+next[k]表示将目标串的本次起始位置pos移动next[k]个单位,这样,新的pos位置与k的距离正好是模式串串首到k的距离。因为原来是pos-->pos+len_m,pos右移到pos+next[k]后,那么距离pos+len_m就是len_m-next[k],正好是模式串串首到k的距离。这种匹配模式思想大体上就是从中间某个字符开始匹配,这样的好处是增大了匹配成功的概率,极大减少了无用匹配次数(如rat="abcabe",mode="abe",mode与tar的前一个"ab"的匹配就是无用匹配,因为第三个字符不再匹配),有些情况下比KMP效率高,并且相对容易理解。
给个实现:

既然是字串匹配新秀,就顺便说说一个更容易理解的模式匹配算法,但论效率个个都是雄于KMP:ZZL算法

相当容易:

序需要两部
预处理
预处理主要完成查找模式串首字符在主串中的所有出现位置,并将其保存在一个数组中。

匹配
在预处理的基础上,字符串匹配算法就可以从查找到的模式串在主串中的位置开始,匹配模式串首字母之后的其余部分。此时,采用BF算法(最闻名而又最笨的字串匹配算法),并可设置一个计数器,记录匹配次数。

实现狠容易,自己看着办— —

PS:本人写博,纯属装X(a<X<c).   本文遵从CC协议,pz伯伯原创,转载注明出处。

这篇关于字符串匹配新秀之Sunday的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/451067

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr

Nginx路由匹配规则及优先级详解

《Nginx路由匹配规则及优先级详解》Nginx作为一个高性能的Web服务器和反向代理服务器,广泛用于负载均衡、请求转发等场景,在配置Nginx时,路由匹配规则是非常重要的概念,本文将详细介绍Ngin... 目录引言一、 Nginx的路由匹配规则概述二、 Nginx的路由匹配规则类型2.1 精确匹配(=)2

Java如何用乘号来重复字符串的功能

《Java如何用乘号来重复字符串的功能》:本文主要介绍Java使用乘号来重复字符串的功能,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java乘号来重复字符串的功能1、利用循环2、使用StringBuilder3、采用 Java 11 引入的String.rep