基于混合策略的单模式匹配算法

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

Single Pattern Matching Algorithms Based on Hybrid Strategy

Two single pattern matching algorithms by combining a smallest suffix automaton and a forward finite state automaton were presented. Whatever the suffix automaton or the forward finite state automaton is running, the window shifts m-R characters and then the smallest suffix automaton starts searching the pattern prefixes from right to left if no pattern prefix is found or R is not greater than half of m,otherwise,the forward finite state automaton starts scanning forwards the corresponding suffixes of the pattern and the new matched prefixes of the pattern is recorded simultaneously.Their time complexities are O(n) in the worst case and O(n/m) in the best case.The experimental results show that their average time complexities are less than that of RF and LDM for short patterns and that of BM for long patterns over small alphabets or short patterns over large alphabets.