کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875866 | 1441989 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Locating maximal approximate runs in a string
ترجمه فارسی عنوان
قرار دادن حداکثر تقریبی اجرا در یک رشته
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های رشته ها، تطبیق الگو، تکرارها، تاندوم تکرار می شود اجرا می شود
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An exact run in a string T is a non-empty substring of T that is a repetition of a smaller substring possibly followed by a prefix of it. Finding maximal exact runs in strings is an important problem and therefore a well-studied one in the area of stringology. For a given string T of length n, finding all maximal exact runs in the string can be done in O(nlogâ¡n) time on general ordered alphabets or O(n) time on integer alphabets. In this paper, we investigate the maximal approximate runs problem: for a given string T and a number k, find non-empty substrings Tâ² of T such that changing at most k letters in Tâ² transforms them into a maximal exact run. We present an O(nk2log2â¡k+occ) algorithm to solve this problem, where occ is the number of substrings found.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 700, 14 November 2017, Pages 45-62
Journal: Theoretical Computer Science - Volume 700, 14 November 2017, Pages 45-62
نویسندگان
Mika Amit, Maxime Crochemore, Gad M. Landau, Dina Sokol,