字符串匹配的sunday算法
28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack
和 needle
,请你在 haystack
字符串中找出 needle
字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle
不是 haystack
的一部分,则返回 -1
。
示例 1:
输入:haystack = "sadbutsad", needle = "sad" 输出:0 解释:"sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ,所以返回 0 。
示例 2:
输入:haystack = "leetcode", needle = "leeto" 输出:-1 解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。
class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ skipped = dict() sub_len = len(needle) for pos, ch in enumerate(needle): skipped[ch] = sub_len - pos i = 0 str_len = len(haystack) while i <= str_len - sub_len: if haystack[i: i + sub_len] == needle: return i if i + sub_len >= str_len: break i += skipped.get(haystack[i+sub_len], sub_len+1) return -1
链接:https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solution/python3-sundayjie-fa-9996-by-tes/
一、Sunday 匹配机制
匹配机制非常容易理解:
目标字符串 haystack
模式串 Pattern当前查询索引 idx (初始为0)
待匹配字符串 haystack [ idx : idx + len(Pattern) ]
每次匹配都会从 目标字符串中 提取 待匹配字符串与 模式串 进行匹配:
若匹配,则返回当前 idx
不匹配,则查看 待匹配字符串 的后一位字符 c:
若c存在于Pattern中,则 idx = idx + 偏移表[c]
否则,idx = idx + len(pattern) + 1
Repeat Loop 直到 idx + len(pattern) > len(String)
举例:
String: checkthisout
Pattern: this
k
不在 Pattern 里- 所以查看 偏移表,
idx = idx + 5
sunday算法核心思想:启发式移动搜索步长!
SUNDAY 算法描述:
字符串查找算法中,最著名的两个是KMP算法(Knuth-Morris-Pratt)和BM算法(Boyer-Moore)。这里介绍一种比BM算法更快一些的sunday查找算法。
例如我们要在"substring searching algorithm"查找"search",刚开始时,把子串与文本左边对齐:
substring searching algorithm
search
^
结果在第二个字符处发现不匹配,于是要把子串往后移动。但是该移动多少呢?这就是各种算法各显神通的地方了,最简单的做法是移动一个字符位 置;KMP是利用已经匹配部分的信息来移动;BM算法是做反向比较,并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字 符(上图中的 'i')。
显然,不管移动多少,这个字符是肯定要参加下一步的比较的,也就是说,如果下一步匹配到了,这个字符必须在子串内。所以,可以移动子串,使子串中的 最右边的这个字符与它对齐。现在子串'search'中并不存在'i',则说明可以直接跳过一大片,从'i'之后的那个字符开始作下一步的比较,如下图:
substring searching algorithm
search
^
比较的结果,第一个字符就不匹配,再看子串后面的那个字符,是'r',它在子串中出现在倒数第三位,于是把子串向前移动三位,使两个'r'对齐,如下:
substring searching algorithm
search
^
哈!这次匹配成功了!回顾整个过程,我们只移动了两次子串就找到了匹配位置,是不是很神啊?!可以证明,用这个算法,每一步的移动量都比BM算法要大,所以肯定比BM算法更快。
因此,对于leetcode上的解题:
https://leetcode.com/problems/implement-strstr/
参考:http://blog.csdn.net/kankan231/article/details/22406823
相关文章
- 字符串匹配算法BF、KCP
- 经典算法题每日演练——第五题 字符串相似度
- Java实现 蓝桥杯 算法提高 数组求和
- Java实现 蓝桥杯VIP 算法提高 字符串比较
- Java实现 蓝桥杯VIP 算法提高 3-2字符串输入输出函数
- Java实现 蓝桥杯VIP 算法提高 分分钟的碎碎念
- Java实现 蓝桥杯VIP 算法提高 前10名
- Java实现 蓝桥杯VIP 算法训练 连接字符串
- Java实现 蓝桥杯VIP 算法训练 入学考试
- Java实现 蓝桥杯VIP 算法训练求先序排列
- Java实现 蓝桥杯VIP 算法训练 字符串逆序
- JAVA-蓝桥杯-算法训练-字符串变换
- 关于KMP算法理解(快速字符串匹配)
- 数据结构与算法之美-12 字符串匹配 BF RK BM KMP Trie AC [MD]
- 【机器学习】机器学习算法总结
- CV之IPE之MobiLenet:基于openpose利用CMU/MobilenetV2算法实现对多人体姿态估计检测(以勒布朗詹姆斯扣篮姿态为例)案例应用
- android 算法题(顺时针打印矩阵,数字字符串反转输出 ,阶乘)
- 数学建模学习(85):人工蜂群优化算法(ABCO)求解多元函数
- 基于粒子群和麻雀搜索的LMS自适应滤波算法 - 附代码
- 1967. 作为子字符串出现在单词中的字符串数目字符串模式匹配-kmp算法和kmp优化算法(双百代码)
- 1763. 最长的美好子字符串-贪心算法
- 1641. 统计字典序元音字符串的数目-动态规划算法
- 单词子集-c语言解决-暴力算法和字符串最大值数判断算法
- 《大数据日知录:架构与算法》试读
- 数据结构——算法之(028)( 寻找当中的一个子字符串个数)
- 数据结构——算法之(010)( 字符串的左旋转操作)
- 深度解读 AlphaGo 算法原理
- 数据结构与算法_09 _ 队列:队列在线程池等有限资源池中的应用
- 字符串匹配KMP算法
- 目标检测算法——垃圾分类数据集汇总(附下载链接)
- 字符串匹配---BF算法--朴素的模式匹配算法
- 试题 算法训练 成绩的等级输出
- 试题 算法训练 最长字符串
- 字符串匹配算法知多少?