Author Archives: hjaltewv

Office hours & an extra hint

Here’s an extra hint for question 2) in the mandatory exercise: For a specific index position i, and a length k, we wish to find all the dual substrings of T of length 2k, where the first half intersects/spans position i in T. You can argue that these dual substrings will all start in a consecutive range [a,b] in T, and that this range can be found using two constant-time LCE queries (one in each direction). Consequently, by repeating for all k, we can output all the dual substrings where the first half intersects position i in O(n+occ) time.

If you have questions about the lecture or the mandatory exercise, you are welcome to come by my office in 322/008 tomorrow (Friday) between 12.00 and 12.30.

– Hjalte

A clarification about the mandatory exercise

Somebody asked what “finding all k-nearly dual substrings in T” means. Just to be completely clear: This means reporting the positions of the substrings of T, which are k-nearly dual strings. That is, output all pairs (i,j), i<j such that T[i..j] is a k-nearly dual string.

– Hjalte