Using binary search on the length of the string, implement a solution with an asymptotic runtime of O(n^2 log n). You should be able to copy the code without changing it, and just rewrite the outer loop longest_substring. Show what the rewritten longest_substring would look like. Be sure that the runtime for the renewed program is O(n^2 log n)

def longest_substring(s, t): """Finds the longest substring that occurs in both s and t""" best = '' return best

def k_substring(s, t, k): """Finds a substring of length k in both s and t if there is one, and returns it. Otherwise, returns None.""" s_substrings = set() # Put all substrings of s of length k into a set: s_substrings for s_start in range(len(s) - k + 1): current = s[s_start:s_start+k] s_substrings.add(current) # For every substring of t of length k, look for it in # s_substrings. If it's there, return it. for t_start in range(len(t)-k+1): current = t[t_start:t_start+k] if current in s_substrings: return current return None