Research and Improvement of the SHIFT-AND Pattern Matching Algorithm

Time performance improvement of the pattern matching mainly lies in reducing the times of character comparisons in each round of matching and increasing the distance that the text string matching window skips to the right when mismatching happens. Based on the above ideas, an improved algorithm based on the combination of word frequency and SHIFT-AND and BMHS2 is proposed. The improved algorithm first uses word frequency matching in each round of matching to reduce the times of character comparisons in matching window. Then, in order to improve the moving distance of the text string matching window when mismatching happens, the BMHS2 and SHIFT-AND algorithms are introduced. Move the text string matching window to the right by the larger skip distance between the SHIFT-AND and BMHS2 algorithms when characters mismatch. The experimental results show that under the same conditions, compared with the SHIFT-AND and BMHS2 algorithms, the improved pattern matching algorithm I_SHIFT-AND_BMHS2 has a certain improvement in matching time performance.