کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871087 1440177 2018 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing longest common extensions in partial words
ترجمه فارسی عنوان
محاسبه طولانی ترین فرمت های رایج در لغات جزئی
کلمات کلیدی
الگوریتم های رشته ها، ترکیبیات بر روی کلمات، توزیع احتمالات، کلمات جزئی، طولانی ترین فرمت های رایج،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The Longest Common Extension of a pair of positions (i,j) in a string, or word, is the longest substring starting at i and j. The LCE problem considers a word and a set of pairs of positions and computes for each pair in the set, the longest common extension starting at both positions in the pair. This problem finds applications in matching with don't-care characters, approximate string searching, finding all exact or approximate tandem repeats, to name a few. From a practical point of view, Ilie et al. (Journal of Discrete Algorithms, 2010) looked for simple and efficient algorithms for the LCE problem. In this paper, we extend their analyses to partial words, strings with don't-cares or holes. We compute the Longest Common Compatible Extension of each pair of positions (i,j) in a partial word, i.e., the longest substrings starting at i and j that are compatible via a combinatorial approach. We also estimate the LCCE of each pair of positions in a partial word via a probabilistic approach. We show that our results match with those of total words (partial words without holes). We find that one of the simplest algorithms for implementing the LCE problem is optimal on average in the context of partial words.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 246, 10 September 2018, Pages 119-139
نویسندگان
, ,