一种快速的字串交叉模式匹配算法

A Fast Algorithm on String Cross Pattern Matching

介绍了一种基于高频字串提取的快速字串交叉模式匹配算法 ,同已有的 KMP、BM等单模式匹配算法和有限自动机等多模式匹配算法相比 ,在字符集Σ较大且字串个数远大于字串最大长度的情况下 ,该算法具有较低的时间复杂度和空间复杂度 ,并适用于字符集较大 。

This paper presented a fast string pattern matching algorithm based on extracting high frequency strings. Compared with the existing algorithms including single pattern algorithms, such as KMP and BM algorithm, and multi pattern matching algorithms, such as DFA, this algorithm has both lower time and space complexity when the size of Σ is large and the number of strings is far more than the max length of string in set U . As Chinese character set is large and the average length of Chinese words is much short, this algorithm is more suitable to process Chinese text.