一种非常快速的字符串匹配算法

• 作者: 刘乃琦 罗大光 郝玉洁
• 来源期刊: 电子科技大学学报
• 学科: 工学
• 关键词: 匹配 散列函数 字符串匹配 快速匹配
• 年，卷（期）: 2005,（6）
• 所属期刊栏目: 学术论文与技术报告
• 页码范围: 802-805
• 页数: 4页
• 分类号: TP311
• 字数: 2750字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0548.2005.06.020

摘要

结合Karp-Rabin和Boyer-Moore字符串匹配算法的优点,提出了一种非常快速的字符串匹配算法.该算法在匹配过程中与传统的直接比较模式及正文子串不同,与KR算法一样,比较的是模式与子串对应的散列值;该算法同时吸取了BM算法的特点,能在扫描正文的过程中跳过尽可能多的字符.理论分析表明,模式串较短时,该算法在最坏情况下的时间复杂度也可以达到O(n).实验表明,该算法所需时间约为KR算法的1/10.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘乃琦	电子科技大学计算机科学与工程学院	47	305	10.0	16.0
2	罗大光	电子科技大学计算机科学与工程学院	4	53	3.0	4.0
3	郝玉洁	电子科技大学计算机科学与工程学院	27	325	11.0	17.0