带记忆的Boyer-Moore型模式匹配算法及其复杂性分析

A Boyer-Moore Type String Matching Algorithm with Memory and Its Computational Complexity

通过构建前缀匹配自动机,使得每轮匹配后下个匹配窗口的文本总是保持左端部分为模式的一个前缀、右端部分全为未比较过的字符的形式.对于与此相应的模式匹配算法,已证明文本内的每个字符在整个匹配过程中最多被比较一次,从而字符总比较次数不超过n,已达到任意算法最坏情况下字符总比较次数的最小值.另外,在适当条件下还从理论上证明了此算法的亚线性(即字符总比较次数小于cn,其中常数c<1).根据实验结果,算法的实际运行速度快于Boyer-Moore算法.

A new string matching automata was constructed. The automata had the advantage that each of the matching windows always kept the uniform form in which the left part in this window was a prefix of the pattern and the characters of the right part were not compared. It has been proved that each of the characters in the text is compared once at most and thus the total compared number in the matching process is less than or equal to the length n of the text. It is minimum in the upper bounds of the total compared numbers of the string matching algorithms in the worst case. When the pattern P is not quasi-cyclic,it has been proved that this algorithm is sublinear, Experiments have shown that the running speed of the algorithm is faster than the BoyerMoore algorithm.