关键词: 模式匹配, KMP算法, BM算法, KMPP算法

Abstract: KMP algorithm and BM algorithm are classical single pattern matching algorithms, because the pointer [i] in the text can only move one character at each time in KMP algorithm, the overall matching efficiency is not high, the improved algorithm（KMPP） accordingly to combine the advantages of the KMP algorithm with BM algorithm together is proposed. The core of KMPP algorithm is when a mismatch occurs at position [j], it calculates the position in the text where the last character of pattern will align with after the pattern moving the value of [next[j]]. If the last character of pattern does not match with the corresponding text position, the bad character rules are applied. The moving distance of pointer [i] in the text is a two-step jumping distance, thus the pointer can move farthest at each time. The experimental result shows that the comparison number of KMPP algorithm is far less than the KMP algorithm’s number and it improves the efficiency of pattern matching algorithm.

Key words: pattern matching, KMP algorithm, BM algorithm, KMPP algorithm