Python培训之怎么实现模式匹配

　　python通过BF算法实现关键词匹配，BF算法，即暴风(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符;若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。

　　代码如下:

　　#!/usr/bin/python

　　# -*- coding: UTF-8

　　# filename BF

　　import time

　　"""

　　t="this is a big apple,this is a big apple,this is a big apple,this is a big apple."

　　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

　　if j==len(p):

　　break

　　elif (j==len(p)-1):

　　count=count+1

　　else:

　　i=i+1

　　j=0

　　print count

　　print time.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相关知识，请关注多测师。https://www.e70w.com/xwzx/