Python基础教程

第一章: 环境搭建,安装Python

第二章: 挑选一款趁手的IDE

第三章: 计算机基础知识

第四章: 命令行基础知识

第五章: 从全局把握Python

第六章: Python语言基础

第七章: Python流程控制

第八章: Python数据类型与运算

第九章: Python字符串类型

第十章: Python列表类型

第十一章: Python元组类型

第十二章: Python字典类型

第十三章: Python集合类型

第十四章: Python函数处理

第十五章: Python文件处理

第十六章: Python面向对象

第十七章: Python异常处理

第十八章: Python模块处理

第十九章: Python高级编程

第二十章: Python项目实战

首页 > Python基础教程 > 第九章: Python字符串类型 > 9.5节: 程序实战-模式匹配算法

9.5节: 程序实战-模式匹配算法

薯条老师 2022-11-30 16:24:09 25806 0

编辑 收藏

广州番禺Python, Java小班周末班培训

薯条老师在广州做Python和Java的小班培训,一个班最多10人,学员的平均就业薪资有11K。不在广州的同学可以报名线上直播班,跟线下小班的同学们同步学习。培训的课程有Python爬虫,Python后端开发,Python办公自动化,Python大数据分析,Python量化投资,Python机器学习,Java中高级后端开发。授课详情请点击:http://chipscoco.com/?cate=6

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 最具实力的小班培训

薯条老师在广州做Python和Java的小班培训,一个班最多10人。不在广州的同学可以报名线上直播班,跟线下小班的同学们同步学习。打算参加小班培训的同学,必须遵守薯条老师的学习安排,认真做作业和项目。把知识学好,学扎实,那么找到一份高薪的工作就是很简单的一件事。

(1) Python后端工程师高薪就业班,月薪11K-18K,免费领取课程大纲
(2) Python爬虫工程师高薪就业班,年薪十五万,免费领取课程大纲
(3) Java后端开发工程师高薪就业班,月薪11K-20K, 免费领取课程大纲
(4) Python大数据分析,量化投资就业班,月薪12K-25K,免费领取课程大纲

扫码免费领取Python学习资料:



欢迎 发表评论: