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 .