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

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