Time-Space Trade-Offs for the Longest Common Substring Problem

Autor:	Tatiana Starikovskaya, Hjalte Wedel Vildhøj
Rok vydání:	2013
Předmět:	Combinatorics Time space Trade offs Space (mathematics) Substring Longest common substring problem Mathematics
Zdroj:	Combinatorial Pattern Matching ISBN: 9783642389047 CPM
DOI:	10.1007/978-3-642-38905-4_22
Popis:	The Longest Common Substring problem is to compute the longest substring which occurs in at least d ≥ 2 of m strings of total length n. In this paper we ask the question whether this problem allows a deterministic time-space trade-off using O(n 1 + e ) time and O(n 1 − e ) space for 0 ≤ e ≤ 1. We give a positive answer in the case of two strings (d = m = 2) and 0 < e ≤ 1/3. In the general case where 2 ≤ d ≤ m, we show that the problem can be solved in O(n 1 − e ) space and O( n 1 + e log2 n (d log2 n + d 2)) time for any 0 ≤ e < 1/3.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::4cd7665d39034ed6bbb9a5e24c74d26d https://doi.org/10.1007/978-3-642-38905-4_22 Zobrazit plný text záznamu