Before revision:  However, when applied to suffix trees, the problem, surprisingly, admits an O(n)-space solution with constant query time  as was shown by Gawrychowski, Lewenstein, and Nicholson .
After revision:  However, when applied to suffix trees, the problem, surprisingly, admits an O(n)-space solution with constant query time as was shown by Gawrychowski, Lewenstein, and Nicholson (Proc. ESA 2014).