Sublinear Space Algorithms for the Longest Common Substring Problem

Tomasz Kociumaka, Tatiana Starikovskaya, Hjalte Wedel Vildhøj

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

Abstract

Given m documents of total length n, we consider the problem of finding a longest string common to at least d ≥ 2 of the documents. This problem is known as the longest common substring (LCS) problem and has a classic O(n) space and O(n) time solution (Weiner [FOCS'73], Hui [CPM'92]). However, the use of linear space is impractical in many applications. In this paper we show that for any trade-off parameter 1 ≤ τ ≤ n, the LCS problem can be solved in O(τ) space and O(n2/τ) time, thus providing the first smooth deterministic time-space trade-off from constant to linear space. The result uses a new and very simple algorithm, which computes a τ-additive approximation to the LCS in O(n2/τ) time and O(1) space. We also show a time-space trade-off lower bound for deterministic branching programs, which implies that any deterministic RAM algorithm solving the LCS problem on documents from a sufficiently large alphabet in O(τ) space must use Ω(n√log(n/(τ log n))/log log(n/(τ log n)) time.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2014 : Proceedings of the 22th Annual European Symposium 2014
EditorsAndreas S. Schulz, Dorothea Wagner
PublisherSpringer
Publication date2014
Pages605-617
ISBN (Print)978-3-662-44776-5
ISBN (Electronic)978-3-662-44777-2
DOIs
Publication statusPublished - 2014
Event22nd Annual European Symposium on Algorithms 2014 - Wroclaw, Poland
Duration: 8 Sep 201410 Sep 2014
Conference number: 22
http://algo2014.ii.uni.wroc.pl/esa/

Conference

Conference22nd Annual European Symposium on Algorithms 2014
Number22
CountryPoland
CityWroclaw
Period08/09/201410/09/2014
OtherESA 2014 is organized in collaboration with the European Association for Theoretical Computer Science (EATCS) and is a part of ALGO 2014.
Internet address
SeriesLecture Notes in Computer Science
Volume8737
ISSN0302-9743

Fingerprint Dive into the research topics of 'Sublinear Space Algorithms for the Longest Common Substring Problem'. Together they form a unique fingerprint.

Cite this