Time-Space Tradeoffs for Finding a Long Common Substring

Stav Ben-Nun, Shay Golan, Tomasz Kociumaka +1

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…