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