文章基本信息

标题：Streaming Periodicity with Mismatches
本地全文：下载
作者：Funda Erg{\"u}n ; Elena Grigorescu ; Erfan Sadeqi Azer 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：42:1-42:21
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.42
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the problem of finding all k-periods of a length-n string S, presented as a data stream. S is said to have k-period p if its prefix of length n-p differs from its suffix of length n-p in at most k locations. We give a one-pass streaming algorithm that computes the k-periods of a string S using poly(k, log n) bits of space, for k-periods of length at most n/2. We also present a two-pass streaming algorithm that computes k-periods of S using poly(k, log n) bits of space, regardless of period length. We complement these results with comparable lower bounds.
关键词：String algorithms; Streaming algorithms; Pattern matching; Randomized algorithms; Sublinear algorithms