python怎么实现模式匹配
python通过BF算法实现关键词匹配,BF算法,即暴风(BruteForce)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。
代码如下:
#!/usr/bin/python
#-*-coding:UTF-8
#filenameBF
importtime
"""
t="thisisabigapple,thisisabigapple,thisisabigapple,thisisabigapple."
p="apple"
"""
t="为什么叫向量空间模型呢?其实我们可以把每个词给看成一个维度,而词的频率看成其值(有向),即向量,这样每篇文章的词及其频率就构成了一个i维空间图,两个文档的相似度就是两个空间图的接近度。假设文章只有两维的话,那么空间图就可以画在一个平面直角坐标系当中,读者可以假想两篇只有两个词的文章画图进行理解。"
p="读者"
i=0
count=0
start=time.time()
while(i<=len(t)-len(p)):
j=0
while(t[i]==p[j]):
i=i+1
j=j+1
ifj==len(p):
break
elif(j==len(p)-1):
count=count+1
else:
i=i+1
j=0
printcount
printtime.time()-start
算法思想:目标串t与模式串p逐词比较,若对应位匹配,则进行下一位比较;若不相同,p右移1位,从p的第1位重新开始比较。
算法特点:整体移动方向:可认为在固定的情况下,p从左向右滑动;匹配比较时,从p的最左边位开始向右逐位与t串中对应位比较。p的滑动距离为1,这导致BF算法匹配效率低(相比其他算法,如:BM,KMP,滑动没有跳跃)。
该算法的时间复杂度为O(len(t)*len(p)),空间复杂度为O(len(t)+len(p))
以上内容为大家介绍了Python培训之怎么实现模式匹配,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注IT培训机构:千锋教育。
相关推荐HOT
更多>>python中ndarray与list转换的方法
python中ndarray与list转换的方法在python数据类型中,list元素可以任意类型组合,而ndarray元素类型必须相同,但是ndarray可以更方便的对多维...详情>>
2023-11-10 08:51:14python中OrdereDict如何使用?
python中OrdereDict如何使用?我们在对数据进行处理时,如果能够使它们保存顺序的排序,那么用起来会非常的便利。不过字典本身就是没有顺序的,...详情>>
2023-11-10 07:05:00python中如何使用scipy.fftpack模块计算快速傅里叶变换?
python中如何使用scipy.fftpack模块计算快速傅里叶变换?在编程中,快速傅里叶变换是工程中非常有价值的一类算法,它可以将时域和频域的信号相互...详情>>
2023-11-10 05:50:23zip()函数如何在python中遍历多个列表?
zip()函数如何在python中遍历多个列表?下面我们就python中zip的说明、语法、使用注意点进行讲解,然后带来遍历多个列表的实例。1、说明zip()函...详情>>
2023-11-10 05:38:33热门推荐
python concat函数有何用法?
沸python里函数装饰器怎么使用?
热如何实现python中的continue语句?
热python中的冒泡排序是什么?
新python中str函数是什么
如何使用python实现项目进度显示?
python中ndarray与list转换的方法
python复制文件的方法整理
Python中numpy数组如何添加元素
python有几种可视化图形库?
python中xlwings是什么?
python上下文管理器的基本介绍
Python自动化测试基础必备知识点一
python中OrdereDict如何使用?