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