一种基于模式最长前缀正文分割的串匹配新算法

A New Algorithm for Pattern Matching in String

字符串的模式匹配问题是计算机科学的基本问题之一 ,本文提出了基于模式最长前缀正文分割的匹配新算法(Text Divided Algorithm,以下简称 TD算法 ) .首先在模式 P中寻找最长的前缀子串 subp,使其末字符在 subp中只出现一次 ;然后根据 subp末字符的特点 ,将正文 T进行分段 ,按段对模式 P进行匹配 .新算法有以下重要的特点 :1.最坏情况下 ,本算法有效地减少了字符重复比较的次数 ,从而提高了算法的匹配效率 ;2 .匹配算法在二维匹配和不精确匹配中较易推广 ;3.匹配过程近似于直接算法 。

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.