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

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

罗大光, 郝玉洁, 刘乃琦

文章导航 > 电子科技大学学报 > 2005 > 34(6): 802-805

罗大光, 郝玉洁, 刘乃琦. 一种非常快速的字符串匹配算法[J]. 电子科技大学学报, 2005, 34(6): 802-805.

引用本文:

罗大光, 郝玉洁, 刘乃琦. 一种非常快速的字符串匹配算法[J]. 电子科技大学学报, 2005, 34(6): 802-805.

LUO Da-guang, HAO Yu-jie, LIU Nai-qi. A Very Fast String Search Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(6): 802-805.

Citation:

LUO Da-guang, HAO Yu-jie, LIU Nai-qi. A Very Fast String Search Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(6): 802-805.

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

1.
电子科技大学计算机科学与工程学院成都 610054

作者简介:
罗大光(1974-),男,硕士,主要从事信息安全、人工智能方面的研究.

中图分类号: TP311

A Very Fast String Search Algorithm

1.
School of Computer Science and Engineering,UEST of China Chengdu 610054

摘要: 结合Karp-Rabin和Boyer-Moore字符串匹配算法的优点,提出了一种非常快速的字符串匹配算法。该算法在匹配过程中与传统的直接比较模式及正文子串不同,与KR算法一样,比较的是模式与子串对应的散列值;该算法同时吸取了BM算法的特点,能在扫描正文的过程中跳过尽可能多的字符。理论分析表明,模式串较短时,该算法在最坏情况下的时间复杂度也可以达到O(n)。实验表明,该算法所需时间约为KR算法的1/10。
- 匹配 /
- 散列函数 /
- 字符串匹配 /
- 快速匹配
Abstract: A very fast algorithm to perform pattern matching in strings was described. The proposed match algorithm combines the advantages of Karp-Rabin's algorithm and Boyer-Moore's algorithm. Instead of checking at each position of the text if the pattern occurs, it is only to check the resemblance between the contents of the string and the pattern by using a hashing function and can skips as many characters as possible. In the cases of short patterns its time complexity can theoretically reach O(n) even in the worst cases. In actual experiments, the time it takes to search a string is about 1/10 of the time KR algorithm takes.
- pattern match /
- hashing function /
- string searching /
- quick search

[1]	周江平, 周媛媛, 周学军, 聂宁. 相位匹配量子密钥分发协议统计波动分析 . 电子科技大学学报, 2023, 52(2): 168-174. doi: 10.12178/1001-0548.2022096
[2]	张菊玲, 郭文强, 杨晓梅, 朱义鑫, 杨国武. 正规式布尔函数NPN等价匹配算法 . 电子科技大学学报, 2023, 52(1): 102-107. doi: 10.12178/1001-0548.2022064
[3]	党涛, 韩垒, 郭谨豪, 欧阳骏. 有源Non-Foster负阻匹配网络及其天线应用 . 电子科技大学学报, 2022, 51(6): 884-889. doi: 10.12178/1001-0548.2020307
[4]	周江平, 周媛媛, 周学军, 聂宁. 二诱骗态相位匹配量子密钥分发方案 . 电子科技大学学报, 2021, 50(5): 650-655. doi: 10.12178/1001-0548.2021171
[5]	吴锋, 高丽敏, 杨彩琼, 冷林涛, 李晓瑜, 陆超. 虚拟试验中基于匹配特性融合的内容网络匹配算法 . 电子科技大学学报, 2021, 50(5): 761-767. doi: 10.12178/1001-0548.2020431
[6]	张菊玲, 杨国武, 吴尽昭, 郭文强. 基于对称及特征的NPN布尔匹配算法 . 电子科技大学学报, 2018, 47(6): 876-881. doi: 10.3969/j.issn.1001-0548.2018.06.012
[7]	吴嘉轩, 代钰, 张斌, 杨雷. 基于拓扑匹配的组件服务副本放置算法 . 电子科技大学学报, 2015, 44(6): 905-910. doi: 10.3969/j.issn.1001-0548.2015.06.019
[8]	陈旦, 杨非, 叶晓俊. 多角度数据库活动监控技术研究 . 电子科技大学学报, 2015, 44(2): 266-271. doi: 10.3969/j.issn.1001-0548.2015.02.018
[9]	康瑞清, 张朝晖, 孙冰. 经验模态分解在地磁匹配导航中的研究 . 电子科技大学学报, 2015, 44(6): 858-862. doi: 10.3969/j.issn.1001-0548.2015.06.011
[10]	李建江, 张磊, 李兴钢, 陈翔, 黄义双. CUDA架构下的灰度图像匹配并行算法 . 电子科技大学学报, 2012, 41(1): 110-113. doi: 10.3969/j.issn.1001-0548.2012.01.021
[11]	牛兰奇, 张太镒, 孙建成. 利用匹配滤波改进MIMO预编码方案 . 电子科技大学学报, 2010, 39(5): 684-687. doi: 10.3969/j.issn.1001-0548.2010.05.008
[12]	王俊芳, 张思东. 通用高速分组交换调度算法 . 电子科技大学学报, 2010, 39(1): 69-73. doi: 10.3969/j.issn.1001-0548.2010.01.017
[13]	张佩云, 黄波, 孙亚民. 面向服务组合的服务语义匹配机制 . 电子科技大学学报, 2008, 37(6): 917-921.
[14]	刘迎辉, 李宏福, 李浩, 王峨锋, 王晖, 王丽. 利用模匹配技术对突变开放腔的分析 . 电子科技大学学报, 2006, 35(4): 494-496.
[15]	万国根, 秦志光. 改进的AC-BM字符串匹配算法 . 电子科技大学学报, 2006, 35(4): 531-533,541.
[16]	尹忠科, 解梅, 王建英. 基于原子能量特性的快速图像匹配追踪 . 电子科技大学学报, 2005, 34(2): 156-159.
[17]	温立, 涂晓东, 王凯. 基于Crossbar的高性能输入排队调度算法对比分析 . 电子科技大学学报, 2004, 33(6): 718-721.
[18]	廖阔, 杨万麟. 点模式指纹匹配算法研究与实现 . 电子科技大学学报, 2004, 33(2): 154-157.
[19]	曾升权, 冯双久, 陈骏莲. Ka频段宽带落入式微带结型隔离器 . 电子科技大学学报, 1997, 26(3): 314-317.
[20]	徐军, 薜泉, 薜良金. 8mm集成鳍线宽带机调耿氏振荡器 . 电子科技大学学报, 1997, 26(1): 35-39.

WeChat

点击查看大图

计量

文章访问数: 3293
HTML全文浏览量: 120
PDF下载量: 74
被引次数: 0

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

1. 电子科技大学计算机科学与工程学院成都 610054

作者简介:
罗大光(1974-),男,硕士,主要从事信息安全、人工智能方面的研究.

收稿日期: 2003-10-08
刊出日期: 2005-12-15

中图分类号: TP311

关键词:

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

English Abstract

罗大光, 郝玉洁, 刘乃琦. 一种非常快速的字符串匹配算法[J]. 电子科技大学学报, 2005, 34(6): 802-805.

引用本文:

罗大光, 郝玉洁, 刘乃琦. 一种非常快速的字符串匹配算法[J]. 电子科技大学学报, 2005, 34(6): 802-805.

LUO Da-guang, HAO Yu-jie, LIU Nai-qi. A Very Fast String Search Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(6): 802-805.

Citation:

LUO Da-guang, HAO Yu-jie, LIU Nai-qi. A Very Fast String Search Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(6): 802-805.

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发