2026-07-24T01:59:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12130 2024-03-06T10:49:22Z ddc:004 open_access

Time-Space Tradeoffs for Finding a Long Common Substring Ben-Nun, Stav Golan, Shay Kociumaka, Tomasz Kraus, Matan longest common substring time-space tradeoff local consistency periodicity We consider the problem of finding, given two documents of total length n, a longest string occurring as a substring of both documents. This problem, known as the Longest Common Substring (LCS) problem, has a classic 𝒪(n)-time solution dating back to the discovery of suffix trees (Weiner, 1973) and their efficient construction for integer alphabets (Farach-Colton, 1997). However, these solutions require Θ(n) space, which is prohibitive in many applications. To address this issue, Starikovskaya and Vildhøj (CPM 2013) showed that for n^{2/3} ≤ s ≤ n, the LCS problem can be solved in 𝒪(s) space and 𝒪̃(n²/s) time. Kociumaka et al. (ESA 2014) generalized this tradeoff to 1 ≤ s ≤ n, thus providing a smooth time-space tradeoff from constant to linear space. In this paper, we obtain a significant speed-up for instances where the length L of the sought LCS is large. For 1 ≤ s ≤ n, we show that the LCS problem can be solved in 𝒪(s) space and 𝒪̃(n²/(L⋅s) +n) time. The result is based on techniques originating from the LCS with Mismatches problem (Flouri et al., 2015; Charalampopoulos et al., CPM 2018), on space-efficient locally consistent parsing (Birenzwige et al., SODA 2020), and on the structure of maximal repetitions (runs) in the input documents. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stav Ben-Nun and Shay Golan and Tomasz Kociumaka and Matan Kraus 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.5 urn:nbn:de:0030-drops-121302 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.5 eng https://creativecommons.org/licenses/by/3.0/legalcode