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

• 作者: 庞善臣 王淑栋
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 串匹配 正文 模式 时间复杂度
• 年，卷（期）: 2004,（3）
• 页码范围: 404-406
• 页数: 3页
• 分类号: TP301
• 字数: 3088字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2004.03.019

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	庞善臣	山东科技大学信息科学与工程学院	19	304	9.0	17.0
2	王淑栋	山东科技大学信息科学与工程学院	30	316	10.0	17.0