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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s