论文部分内容阅读
结合后缀有限自动机和正向有限自动机的优点，提出了两个单模式匹配算法．算法中，无论是后缀自动机还是正向有限自动机，只要扫描到的模式前缀长度R〉0或者超过模式长度的1／2时，使用正向有限自动机继续向右进行扫描；否则都滑动m—R个字符，使用后缀自动机反向扫描模式串的前缀．两个算法的最差、最好时间复杂度分别为O（72）和O（n／m）．结果表明，在短模式的情况下，两个算法的平均时间复杂度均好于RF和LDM，在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM．