| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10331932 | Information Processing Letters | 2005 | 7 Pages |
Abstract
We consider the problem of designing an efficient index for approximate pattern matching. Despite ongoing efforts, this topic is still a challenge in combinatorial pattern matching. We present a new data structure that allows to report all matches in worst-case time O(|Σ|m+occ), which is linear in the pattern length m and the number of occurrences occ for alphabets of constant size |Σ|. Our index uses O(n|Σ|logn) extra space on average and with high probability, where n is the length of the text (indexing) or the number of strings to index (dictionary lookup).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Moritz G. MaaÃ, Johannes Nowak,