کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431605 688594 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on the longest common compatible prefix problem for partial words
ترجمه فارسی عنوان
یک یادداشت در مورد طولانی ترین پیشوند سازگار مشترک برای کلمات جزئی
کلمات کلیدی
کلمه جزئی، طولانی ترین پیشوند سازگار با استاندارد، طولانی ترین پیشوند مشترک، برنامه نویسی پویا
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

For a partial word w the longest common compatible prefix of two positions i, j  , denoted lccp(i,j)lccp(i,j), is the largest k   such that w[i,i+k−1]w[i,i+k−1] and w[j,j+k−1]w[j,j+k−1] are compatible. The LCCP problem is to preprocess a partial word in such a way that any query lccp(i,j)lccp(i,j) about this word can be answered in O(1)O(1) time. We present a simple solution to this problem that works for any linearly-sortable alphabet. Our preprocessing is in time O(nμ+n)O(nμ+n), where μ is the number of blocks of holes in w.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 34, September 2015, Pages 49–53
نویسندگان
, , , , , , , , ,