一种模式匹配快速算法

计算机科学 ›› 2008, Vol. 35 ›› Issue (1): 219-220.

一种模式匹配快速算法

刘玉龙刘啸

徐州师范大学计算机学院徐州师范大学现代教育技术中心,徐州221116

出版日期:2018-11-16 发布日期:2018-11-16

LIU Yu-Long LIU Xiao （College of Computer ,Center of Modern Education Technology ,Xuzhou Normal University, Xuzhou 221116）

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 在定义模式串的特征值之后，给出了判断两等长串匹配的必要条件以及两相邻子串的特征值之间的递推关、系。在此基础上，提供一种模式匹配快速算法，其时间复杂度可达O（n）。该算法彻底避免了回溯现象，执行效率要比RK算法高。

关键词: 串模式模式匹配特征值递推

Abstract: After introducing the definition of a string＇s eigenvalue ,necessary conditions used to judge if two strings having equal lengths are matched, and a recurrence relation between the eigenvalues of two adjacent substrings are given. Then a fast string-match

Key words: String, Pattern, String-matching, Eigenvalue,Recursion

刘玉龙刘啸. 一种模式匹配快速算法[J]. 计算机科学, 2008, 35(1): 219-220. https://doi.org/

LIU Yu-Long LIU Xiao （College of Computer ,Center of Modern Education Technology ,Xuzhou Normal University, Xuzhou 221116）. [J]. Computer Science, 2008, 35(1): 219-220. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed