黑松山资源网 Design By www.paidiu.com
基本的字符串位置查找方法
Python 查找字符串使用 变量.find("要查找的内容"[,开始位置,结束位置]),开始位置和结束位置,表示要查找的范围,为空则表示查找所有。查找到后会返回位置,位置从0开始算,如果每找到则返回-1。
str = 'a,hello' print str.find('hello') # 在字符串str里查找字符串hello 2 # 输出结果
朴素匹配算法
朴素匹配算法是对目标字符串和模板字符串的一一匹配。如果匹配得上,下标向右移一位, 否则清空并重新开始匹配。
target = 'abb aba' pattern = 'aba' def match(target, pattern): i = j = 0 n, m = len(target), len(pattern) while i < n and j < m: # 如果字符相等则目标和模板的下标都向右移 if target[i] == pattern[j]: i, j = i+1, j+1 else: # 如果字符不相等则目标下标切换到不相等的下标 # 模板下标移动到初始下标 i = i - j + 1 j = 0 if j == m: return i - j return -1
把上面的加上print后打印一遍
#修改的地方 else: i = i -j + 1 j = 0 print(target[i], pattern[j], i, j) # 打印结果 b a 1 0 b a 2 0 a 3 0 a a 4 0
循环会一直到相等的匹配值, 这个方法效率低下,主要是在不匹配时会重新把模板字符循环一次。最多可能会出现 m * (n-m +1)次。m是模板字符的长度,n-m + 1是排除不等字符的次数。
KMP 算法
kmp是通过已知匹配的字符进行移位的算法,比如上面的abb 中跟abc比较的话 ab是已知的。
def match(target, pattern): i = j = 0 n, m = len(target), len(pattern) while i < n and j < m: # 如果字符相等则目标和模板的下标都向右移 if if j == -1 and target[i] == pattern[j]: i, j = i+1, j+1 else: # 这里通过next 函数来判断位移个数 i = i - j + pattern_next(pattern[:j]) j = 0 if j == m: return i - j return -1 def pattern_next(s): prefix = [s[:i+1] for i in range(len(s)-1)] suffix = [s[i+1:] for i in range(len(s)-1)] l = list(set(prefix) & set(suffix)) return len(l)
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月09日
2024年10月09日
- s14全球总决赛瑞士轮赛制是什么 全球总决赛瑞士轮赛制详情
- 《COD21》全新剧情宣传片:10月25日XGP见!
- 美国拳王家门口身中7枪遇害 年仅31岁凶手仍未被逮捕
- 《寂静岭2》重制版光追对比:氛围更加恐怖
- 林慧萍.1982-往昔(飞跃复刻版)【歌林】【WAV+CUE】
- 陈楚生.2007-原来我一直都不孤单(EP)【天娱传媒】【WAV+CUE】
- 罗嘉良.1986-秦始皇(2014环球复黑王·百代篇)【EMI百代】【WAV+CUE】
- 2024周年庆赠送物品介绍,周年庆送什么
- 【原神】V5.0攻略 |「明黄曜石断片」全收集
- 【原神】V5.0攻略 | 隐藏成就「烦请高抬贵脚」达成
- 证声音乐图书馆《蔚蓝海岸·爵士度假日》[FLAC/分轨][155.47MB]
- 腾讯音乐人《浪漫火焰(新势力计划合辑 Vol.11)》[320K/MP3][56.91MB]
- 腾讯音乐人《浪漫火焰(新势力计划合辑 Vol.11)[FLAC/分轨][147.45MB]
- 2024年,哪里还可以玩有趣的魔兽RPG?
- 类银河恶魔城动作游戏《灵魂熔解》已正式登陆Steam