9.5.1 何为模式匹配?
模式匹配是数据结构中字符串的一种基本运算: 给定一个子串,要求在主串中找出与该子串相同的所有子串,这就是模式匹配。举个简单的例子,主串为"中国人不欺压中国人",子串为"中国"。这里的子串即是待匹配的模式, 找出主串"中国人不欺压中国人"中的所有模式"中国",就是一个模式匹配。
9.5.2 朴素模式匹配算法
本节要实现的是一个非常简单的朴素模式匹配算法,我们先来掌握朴素模式匹配算法的基本思想:
从主串的第一个字符起与模式串的第一个字符比较,如果相等,则继续对字符进行后续的比较,否则从主串的第二个字符起与模式串的第一个字符重新比较,不断重复这样的过程,直至模式串中的每个字符依次和主串中的一个连续的字符序列相等为止,此时称为匹配成功,否则匹配失败。
根据以上思想,我们使用Python语言来实现字符串的朴素模式匹配算法:
""" @author: 薯条老师 @desc: 实现字符串的朴素模式匹配算法 """ # master为主串 master = "中国人不欺压中国人,点赞中国" # 模式为中国 pattern = "中国" # 通过len方法计算主串和模式串的长度 length_of_master = len(master) length_of_pattern = len(pattern) # begin为0, 表示从主串的第一个位置开始比较 begin = 0 while begin <= length_of_master-length_of_pattern: """ begin为什么要小于等于主串的长度减去模式串的长度? (1) 如果模式串长度大于主串,那么模式串一定不存在, 此时length_of_master-length_of_pattern小于0,while后面的表达式为假 (2) 如果模式串长度小于等于主串,那么在主串中移动时,最多只移动 length_of_master-length_of_pattern的距离。 也就是移动到模式串和主串右对齐时的起始位置: 中国 中国人不欺压中国人 """ if master[begin] == pattern[0]: # 定义pos变量,用来保存主串中的起始位置 pos = begin # 使用for循环遍历模式字符串中的每一个字符 for ch in pattern: # 主串字符在与模式字符比较的过程中,只要一个字符不相等就停止匹配 if master[pos] != ch: break # 在主串中每比较完一个字符,就需要往前移动一个位置,所以+1 pos += 1 else: # for循环结构的else表示在循环中没有执行break后的收尾操作 # 既然没有执行break, 就说明找到了模式 print(begin) # 思考题,为什么begin要加上 length_of_pattern再减1? begin += length_of_pattern-1 begin += 1
9.5.3 最具实力的小班培训
薯条老师在广州有开设线下培训班,小班授课模式,一班最多6个人。也可一对一授课,全程帮助你学好计算机,实现高薪就业。不在广州的同学可提供住宿,也可以报名线上小班,用腾讯会议上直播课。
(1) Python后端工程师高薪就业班,月薪11K-18K,免费领取课程大纲
(2) Python中高级爬虫逆向工程师就业班,月薪15K-25K,包拿Offer
(3) Python数据分析+商业分析+数据科学就业班,企业级项目实战,月薪10K-20K
(4) Python量化交易就业班,A股+期货+数字货币量化,月薪10K-40K
(5) Python机器学习+深度学习算法工程师,月薪20-50K
跟薯条老师学习的学生有拿到花生日记,林氏家居,南方电网,京东, 阿里等公司的offer, 学生的最低薪资有6K,最高薪资有18K, 平均就业薪资有11000。
扫码咨询薯条老师: