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培训机构:千锋教育。

声明：本站部分稿件版权来源于网络，如有侵犯版权，请及时联系我们。