文章基本信息

标题：Quasi-Periodicity in Streams
本地全文：下载
作者：Pawel Gawrychowski ; Jakub Radoszewski ; Tatiana Starikovskaya 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：128
页码：1-14
DOI：10.4230/LIPIcs.CPM.2019.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this work, we show two streaming algorithms for computing the length of the shortest cover of a string of length n. We start by showing a two-pass algorithm that uses O(log^2 n) space and then show a one-pass streaming algorithm that uses O(sqrt{n log n}) space. Both algorithms run in near-linear time. The algorithms are randomized and compute the answer incorrectly with probability inverse-polynomial in n. We also show that there is no sublinear-space streaming algorithm for computing the length of the shortest seed of a string.
关键词：Streaming algorithms; quasi-periodicity; covers; seeds