The factors analysis and algorithm implementation of single-pattern matching |
| |
Authors: | Gong-shen Liu Sheng-jun Zhu |
| |
Institution: | (1) School of Information Security Engineering, Shanghai Jiaotong University, Shanghai, 200240, China |
| |
Abstract: | By studying the algorithms of single pattern matching, five factors that have effect on time complexity of the algorithm are
analyzed. The five factors are: sorting the characters of pattern string in an increasing order of using frequency, utilizing
already-matched pattern suffix information, utilizing already-matched pattern prefix information, utilizing the position factor
which is absorbed from quick search algorithm, and utilizing the continue-skip idea which is originally proposed by this paper.
Combining all the five factors, a new single pattern matching algorithm is implemented. It’s proven by the experiment that
the efficiency of new algorithm is the best of all algorithms.
Foundation item: the National Natural Science Foundation of China (Nos. 60502032 and 60672068) |
| |
Keywords: | single pattern matching string search algorithm analysis |
本文献已被 维普 SpringerLink 等数据库收录! |
|