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 的第一位开始。

算法特点： 整体移动方向：可以认为在固定条件下，p从左向右滑动；匹配比较时，从p的最左边开始向右，与t字符串中的对应位逐位比较。 p的滑动距离为1，导致BF算法匹配效率低（与其他算法相比，如：BM、KMP，滑动没有跳跃）。

该算法的时间复杂度为O（len(t)*len(p))，空间复杂度为O(len(t)+len(p))