کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950837 | 1441037 | 2017 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tight lower bounds for the longest common extension problem
ترجمه فارسی عنوان
محدوده تنگ پایین برای طولانی ترین مشکل گسترش مشترک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
طولانی ترین فرمت رایج، ساختارهای داده، مصالحه، مرزهای پایین، مدل پروب سلولی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The longest common extension problem is to preprocess a given string of length n into a data structure that uses S(n) bits on top of the input and answers in T(n) time the queries LCE(i,j) computing the length of the longest string that occurs at both positions i and j in the input. We prove that the trade-off S(n)T(n)=Ω(nlogâ¡n) holds in the non-uniform cell-probe model provided that the input string is read-only, each letter occupies a separate memory cell, S(n)=Ω(n), and the size of the input alphabet is at least 28âS(n)/nâ. It is known that this trade-off is tight.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 125, September 2017, Pages 26-29
Journal: Information Processing Letters - Volume 125, September 2017, Pages 26-29
نویسندگان
Dmitry Kosolobov,