| Abstract: | We study the classical approximate string matching problem, that is, given strings P and Q and an error threshold k, find all ending positions of substrings of Q whose edit distance to P is at most k. Let P and Q have lengths m and n, respectively. On a standard unit-cost word RAM with word size w≥log n we present an algorithm using time | O(nk ·min(fraclog2 mlogn,fraclog2 mlogww) + n)Obiggl(nk cdot minbiggl(frac{log^2 m}{log n},frac{log^2 mlog w}{w}biggr) + nbiggr) |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
