|
|||||
|
|
Edit distance of run-length encoded strings |
|
| Authors: | Ora Arbell Gad M Landau Joseph SB Mitchell |
| Affiliation: | a Department of Computer Science, Haifa University, Haifa 31905, Israel b Department of Computer and Information Science, Polytechnic University, Six MetroTech Center, Brooklyn, NY 11201-3840, USA c Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY 11794-3600, USA |
| Abstract: | Let X and Y be two run-length encoded strings, of encoded lengths k and l, respectively. We present a simple O(|X|l+|Y|k) time algorithm that computes their edit distance. |
| Keywords: | String matching Dynamic programming Run-length compression Edit distance Algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |