Abstract:

The BM algorithm is a  more efficient single pattern matching algorithm. The common method of improving the BM algorithm is to start with increasing the probability of the first failure character matching and the maximal moving distance of the matching window. At the same time, the higher cost of accessing memory counteracts the actual efficiency of the new algorithm. Optimizing the number of the lookup table and the times of accessing memory when it moves the key distance of the matching window, and DCSBM makes good use of the double character’s first failure matching probability at the cost of reducing the key steps properly. It is tested that DCSBM obviously increases the average moving distance of the matching window. In larger length of the text or pattern, the real efficiency of DCSBM is higher than BM, BMHS, or BMN algorithm.

Key words: pattern matching;double character sequence;BM algorithm;BMHS algorithm