| 一种模式匹配快速算法 |
| |
| 引用本文： | 刘玉龙 刘啸. 一种模式匹配快速算法[J]. 计算机科学, 2008, 35(1): 219-220 |
| |
| 作者姓名： | 刘玉龙 刘啸 |
| |
| 作者单位： | 徐州师范大学计算机学院,徐州,221116;徐州师范大学现代教育技术中心,徐州,221116 |
| |
| 摘 要： | 在定义模式串的特征值之后,给出了判断两等长串匹配的必要条件以及两相邻子串的特征值之间的递推关系.在此基础上,提供一种模式匹配快速算法,其时间复杂度可达O(n).该算法彻底避免了回溯现象,执行效率要比RK算法高.
|
| 关 键 词： | 串 模式 模式匹配 特征值 递推 |
A Fast String-matching Algorithm |
| |
| LIU Yu-Long LIU Xiao (College of Computer,Center of Modern Education Technology,Xuzhou Normal University,Xuzhou. A Fast String-matching Algorithm[J]. Computer Science, 2008, 35(1): 219-220 |
| |
| Authors: | LIU Yu-Long LIU Xiao (College of Computer Center of Modern Education Technology Xuzhou Normal University Xuzhou |
| |
| 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-matching algorithm which expected running time is O(n)is presented.The algorithm is more effective than RK algorithm and avoiding all backtrackings thoroughly. |
| |
| Keywords: | String Pattern String-matching Eigenvalue Recursion |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
