کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428121 686603 2007 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edit distance for a run-length-encoded string and an uncompressed string
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Edit distance for a run-length-encoded string and an uncompressed string
چکیده انگلیسی

We propose a new algorithm for computing the edit distance of an uncompressed string against a run-length-encoded string. For an uncompressed string of length n and a compressed string with M runs, the algorithm computes their edit distance in time O(Mn). This result directly implies an O(min{mN,Mn}) time algorithm for strings of lengths m and n with M and N runs, respectively. It improves the previous best known time bound O(mN+Mn).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 105, Issue 1, 31 December 2007, Pages 12-16