摘要：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 ð'ªÌf(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 ð'ªÌf(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.
关键词：longest common substring; time-space tradeoff; local consistency; periodicity
