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

Tatiana Starikovskaya; Hjalte Wedel Vildhøj

doi:10.1007/978-3-642-38905-4_22

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

Tatiana Starikovskaya
, Hjalte Wedel Vildhøj

Department of Applied Mathematics and Computer Science

Lomonosov Moscow State University

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Combinatorial Pattern Matching : 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings
Publisher	Springer
Publication date	2013
Pages	223-234
ISBN (Print)	978-3-642-38904-7
ISBN (Electronic)	978-3-642-38905-4
DOIs	https://doi.org/10.1007/978-3-642-38905-4_22
Publication status	Published - 2013
Event	24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013) - Bad Herrenalb, Germany Duration: 17 Jun 2013 → 19 Jun 2013 http://www.cpm2013.de/

Conference

Conference	24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013)
Country/Territory	Germany
City	Bad Herrenalb
Period	17/06/2013 → 19/06/2013
Internet address	http://www.cpm2013.de/

Series	Lecture Notes in Computer Science
Volume	7922
ISSN	0302-9743

Access to Document

10.1007/978-3-642-38905-4_22

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{58c269952165482da75a02b2b5cc4a7d,

title = "Time-Space Trade-Offs for the Longest Common Substring Problem",

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.",

author = "Tatiana Starikovskaya and Vildh{\o}j, \{Hjalte Wedel\}",

year = "2013",

doi = "10.1007/978-3-642-38905-4\_22",

language = "English",

isbn = "978-3-642-38904-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "223--234",

booktitle = "Combinatorial Pattern Matching",

note = "24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013) ; Conference date: 17-06-2013 Through 19-06-2013",

url = "http://www.cpm2013.de/",

}

Starikovskaya, T & Vildhøj, HW 2013, Time-Space Trade-Offs for the Longest Common Substring Problem. in Combinatorial Pattern Matching: 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings. Springer, Lecture Notes in Computer Science, vol. 7922, pp. 223-234, 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), Bad Herrenalb, Germany, 17/06/2013. https://doi.org/10.1007/978-3-642-38905-4_22

Time-Space Trade-Offs for the Longest Common Substring Problem. / Starikovskaya, Tatiana; Vildhøj, Hjalte Wedel.
Combinatorial Pattern Matching: 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings. Springer, 2013. p. 223-234 (Lecture Notes in Computer Science, Vol. 7922).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

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

AU - Starikovskaya, Tatiana

AU - Vildhøj, Hjalte Wedel

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-38905-4_22

DO - 10.1007/978-3-642-38905-4_22

M3 - Article in proceedings

SN - 978-3-642-38904-7

T3 - Lecture Notes in Computer Science

SP - 223

EP - 234

BT - Combinatorial Pattern Matching

PB - Springer

T2 - 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013)

Y2 - 17 June 2013 through 19 June 2013

ER -

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

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this