کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875887 1441991 2017 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
String cadences
ترجمه فارسی عنوان
رشته ها
ترجمه چکیده
در این مقاله ما یک مطالعه سیستماتیک از کارایی یافتن رساله ها را آغاز می کنیم. ابتدا برخی تعاریف اولیه را ارائه می دهیم؛ سپس یک الگوریتم فرعی دو بعدی برای تعیین اینکه آیا یک رشته دارای هر کدام از حداقل سه رخداد یک شخصیت است، و یک الگوریتم تقریبا خطی برای یافتن همه جاذبه های مجاز است؛ در نهایت، ما یک ساختار داده ای را ارائه می دهیم که ویژگی های بسیاری از ویژگی ها را در بر می گیرد و اجازه می دهد تا تشخیص کارآمد بسیاری از انواع داده ها انجام شود. به طور خاص، تمام فرکانس ها را می توان در زمان های مختلف تشخیص و گزارش داد که متناسب با مجموع طول آنها باشد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we begin a systematic study of the efficiency of finding cadences. We first give some basic definitions; we then give a sub-quadratic algorithm for determining whether a string has any cadence consisting of at least three occurrences of a character, and a nearly linear algorithm for finding all anchored cadences; finally, we propose a data structure that captures many features of cadences and allows for the efficient detection of many types of cadences. In particular, all sub-cadences can be detected and reported in time proportional to the sum of their lengths.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 698, 25 October 2017, Pages 4-8
نویسندگان
, , , ,