关键词: 串匹配, BM算法, 好后缀规则, shift函数, 复杂度分析

Abstract: For the research and improvement of Boyer-Moore (BM) algorithm and its variants, it is very necessary to establish strict formal theory of the function shift in Boyer-Moore's and its construction algorithm. A clear formal definition of shift was given. Then, characteristic sets of the pattern suffixes and its minimum value function were introduced, and the construction of shift was described by the characteristic sets, thus theoretical basis of shift and its construction algorithm were strictly established. Finally, a new construction algorithm of shift was presented based on the construction theorem of shift and iterative computing method of the minimum value function. It is proved that the algorithm has linear time and space complexity. The theoretical analysis and computing results show that the algorithm is simpler, and its complexity of computation is lower, so it is more suitable for hardware implementation compared with several existing algorithms.

Key words: string matching, Boyer-Moore (BM) algorithm, good-suffix rule, function shift, complexity analysis