A New Algorithm for Pattern Matching in String
Pang Shan-chen · Mini-micro Systems · 2004
In this paper, we present a new algorithm of pattern-matching in string(Text Divided Algorithm) .The idea of the algorithm is as follows: Firstly, we find the longest prefix substring of pattern P, named as subp, such that its end-letter appears only once in the subp. Secondly, we divide the text T into several sections according to the characters of the end-letter of subp, then match P with every section of T. The important characters of the new algorithm are stated as follows: 1. The complexity of the algorithm is reduced efficiently; 2. The matching algorithm is more easily extended to two dimensions and approximate matching; 3. The matching process is similar to the direct algorithm, and convenient to accept and understand.