Research of Pattern Matching Algorithm Based on KMP and BMHS2
Yansen Zhou, Ruixuan Pang · 2019
The improvement of the time performance of pattern matching algorithm mainly lies in reducing the number of character comparisons and increasing the distance of the matching window moving to the right when mismatch. In this paper, it adopts the second idea of improvement. The paper first analyzes KMP algorithm and its improved one, and then introduces BMHS2 algorithm. The distance of moving to the right of two improved algorithms is calculated when mismatch occurs respectively, and then proposes an improved algorithm based on the combination of improved KMP and BMHS2. The idea of this matching algorithm is that the overall matching is carried out from left to right, and every time the matching is carried out from left to right. When the text substring in matching window is mismatched with the pattern string, the larger jump distance of the I_KMP and BMHS2 is adopted to move the matching window to the right. Finally, two experiments to compare the time performance of the three algorithms above are carried out. The result shows that in the same experiment condition, compared to improved KMP and BMHS2, the time performance of improved pattern matching algorithm I_KMP_BMHS2 improved to some extent.