FIX to Position-Restricted Substring Searching
Level: Medium
There is an error when we say that we can count the number of occurrences
of a position-restricted pattern in time O(m + log log n) using
O(n log^(1+e) n) bits of space. The error came from our
misinterpretation of a result in computational geometry. The time is
O(m + log n / log log n), and can be achieved with O(n log n)
bits of space.
Fortunately this result is not very central to the paper. Yet, the result is
mentioned in the abstract, Introduction (including Table 1), and then in
Section 3, last lines of subsection "Larger and faster".
This issue was communicated to us by Moshe Lewenstein, Bar-Ilan University,
Israel.