时间:2021-05-22
基本的字符串位置查找方法
Python 查找字符串使用 变量.find("要查找的内容"[,开始位置,结束位置]),开始位置和结束位置,表示要查找的范围,为空则表示查找所有。查找到后会返回位置,位置从0开始算,如果每找到则返回-1。
朴素匹配算法
朴素匹配算法是对目标字符串和模板字符串的一一匹配。如果匹配得上,下标向右移一位, 否则清空并重新开始匹配。
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 0b a 2 0 a 3 0a 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 -1def 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)声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了python实现在字符串中查找子字符串的方法。分享给大家供大家参考。具体如下:这里实现python在字符串中查找子字符串,如果找到则返回子字符串的
本文实例讲述了python开发之字符串string操作方法。分享给大家供大家参考,具体如下:在python中,对于字符串string的操作,我们有必要了解一下,
这次主要介绍字符串常用操作方法及例子1.python字符串在python中声明一个字符串,通常有三种方法:在它的两边加上单引号、双引号或者三引号,如下:name
python字符串替换是python操作字符串的时候经常会碰到的问题,这里简单介绍下字符串替换方法。python字符串替换可以用2种方法实现:1是用字符串本身的
本文实例为大家分享了python字符串的操作方法,供大家参考,具体内容如下1.去除空格str.strip():删除字符串两边的指定字符,括号的写入指定字符,默认