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

Tatiana Starikovskaya, Hjalte Wedel Vildhøj

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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(n1+ε) time and O(n1-ε) space for 0 ≤ ε ≤ 1. We give a positive answer in the case of two strings (d = m = 2) and 0 <ε ≤ 1/3. In the general case where 2 ≤ d ≤ m, we show that the problem can be solved in O(n1-ε) space and O(n1+ε log2n (d log2n + d2)) time for any 0 ≤ ε <1/3.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching : 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings
PublisherSpringer
Publication date2013
Pages223-234
ISBN (Print)978-3-642-38904-7
ISBN (Electronic)978-3-642-38905-4
DOIs
Publication statusPublished - 2013
Event24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013) - Bad Herrenalb, Germany
Duration: 17 Jun 201319 Jun 2013
http://www.cpm2013.de/

Conference

Conference24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013)
Country/TerritoryGermany
CityBad Herrenalb
Period17/06/201319/06/2013
Internet address
SeriesLecture Notes in Computer Science
Volume7922
ISSN0302-9743

Cite this