The Factors Analysis and Algorithm Implementation of Single-pattern Matching

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, utili...

Full description

Saved in:
Bibliographic Details
Published in:Shanghai jiao tong da xue xue bao 2009-06, Vol.14 (3), p.331-337
Main Author: 刘功申 朱圣军
Format: Article
Language:English
Subjects:
Architecture
Computer Science
Electrical Engineering
Engineering
Life Sciences
Materials Science
匹配模式
因素影响
字符串
学习算法
快速搜索算法
时间复杂度
模式匹配算法
算法实现
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1007-1172
1995-8188
DOI:10.1007/s12204-009-0331-9