Python USES BF algorithm to implement keyword matching method

This paper illustrates the method of keyword matching by BF algorithm in python. Share with you for your reference. The specific implementation method is as follows:

#!/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=" Why is it called a vector space model? In fact, we can think of each word as a dimension, and the frequency of the word as its value (directed), that is, a vector, so that each article of the word and its frequency constitute a i Dimensional space graph, the similarity of two documents is the proximity of two space graphs. If the article only has two dimensions, then the spatial graph can be drawn in a plane cartesian coordinate system, the reader can imagine two articles with only two words to draw a picture to understand. "

p=" The reader "

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

 
Algorithm idea: target string t and pattern string p are compared word by word. If the corresponding bit matches, the next bit is compared. If not, shift p one bit to the right and start the comparison again from the first bit of p.

Algorithm features: overall movement direction: it can be considered that p slides from left to right under fixed conditions; When matching comparison, start from the leftmost bit of p to the right to compare bit by bit with the corresponding bit in the t string. The sliding distance of p is 1, which leads to the low matching efficiency of BF algorithm (compared with other algorithms, such as BM, KMP, sliding has no jump).

The time complexity of this algorithm is O(len(t) *len(p)), and the space complexity is O(len(t)+len(p)).

I hope this article has helped you with your Python programming.