A Subquadratic Algorithm for Approximate Regular Expression Matching |
| |
| Authors: | Wu S. Manber U. Myers E. |
| |
| Affiliation: | 1. Institute of Informatics, University of Warsaw, Poland;2. Helsinki Institute for Information Technology HIIT, Department of Computer Science, Aalto University, Finland;1. INESC-ID and Instituto Superior Técnico, Universidade de Lisboa, Portugal;2. Department of Computer Science, Kyushu University, Japan;1. Department of Computer and Information Engineering, Inha University, Incheon 402-751, South Korea;2. Department of Computer Science and Engineering, Sejong University, Seoul 143-747, South Korea;3. School of Computer Science and Engineering, Seoul National University, Seoul 151-742, South Korea |
| |
| Abstract: | The main result of this paper is an algorithm for approximate matching of a regular expression of size m in a text of size n in time O(nm/logd+2n), where d is the number of allowed errors. This algorithm is the first o(mn) algorithm for approximate matching to regular expressions. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
