| 一种非常快速的字符串匹配算法 |
| |
| 引用本文： | 罗大光,郝玉洁,刘乃琦. 一种非常快速的字符串匹配算法[J]. 电子科技大学学报(自然科学版), 2005, 34(6): 802-805 |
| |
| 作者姓名： | 罗大光 郝玉洁 刘乃琦 |
| |
| 作者单位： | 电子科技大学计算机科学与工程学院,成都,610054;电子科技大学计算机科学与工程学院,成都,610054;电子科技大学计算机科学与工程学院,成都,610054 |
| |
| 摘 要： | 结合Karp-Rabin和Boyer-Moore字符串匹配算法的优点,提出了一种非常快速的字符串匹配算法。该算法在匹配过程中与传统的直接比较模式及正文子串不同,与KR算法一样,比较的是模式与子串对应的散列值;该算法同时吸取了BM算法的特点,能在扫描正文的过程中跳过尽可能多的字符。理论分析表明,模式串较短时,该算法在最坏情况下的时间复杂度也可以达到O(n)。实验表明,该算法所需时间约为KR算法的1/10。
|
| 关 键 词： | 匹配 散列函数 字符串匹配 快速匹配 |
| 收稿时间： | 2003-10-08 |
| 修稿时间： | 2003-10-08 |
A Very Fast String Search Algorithm |
| |
| 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 |
| |
| Authors: | LUO Da-guang HAO Yu-jie LIU Nai-qi |
| |
| Affiliation: | 1.School of Computer Science and Engineering,UEST of China Chengdu 610054 |
| |
| 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. |
| |
| Keywords: | pattern match hashing function string searching quick search |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《电子科技大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《电子科技大学学报(自然科学版)》下载全文 |
|
