Sublinear Space Algorithms for the Longest Common Substring Problem

Abstract. Given m documents of total length n, we consider the prob-lem of finding a longest string common to at least d ≥ 2 of the docu-ments. 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 imprac-tical 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 im-plies that any deterministic RAM algorithm solving the LCS problem on documents from a sufficiently large alphabet in O(τ) space must us