python通过BF算法实现关键词匹配，pythonbf,python通过BF算法

python通过BF算法实现关键词匹配```python

!/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=0count=0start=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=0print countprint 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))