Conference paper
Time-Space Trade-Offs for the Longest Common Substring Problem
In
Lecture Notes in Computer Science
—
2013, pp. 223-234
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.
| Language: | English |
|---|---|
| Publisher: | Springer |
| Year: | 2013 |
| Pages: | 223-234 |
| Proceedings: | 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013)Annual Symposium on Combinatorial Pattern Matching |
| Series: | Lecture Notes in Computer Science |
| Journal subtitle: | 24th Annual Symposium, Cpm 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings |
| ISBN: | 364238904X , 364238904x , 3642389058 , 9783642389047 and 9783642389054 |
| ISSN: | 03029743 |
| Types: | Conference paper |
| DOI: | 10.1007/978-3-642-38905-4_22 |
