題組內容

6. Consider a 3-gram index below, where 3-gram refers to a string of 3 characters, and the index refers to a link list whose nodes are the vocabulary containing the 3-gram. For instance, the first node in the list is “beetroot”, which contains the 3-gram “etr”. Note that in this data structure, vocabulary terms are lexicographically ordered.6167a59fda972.jpg

(b) (15%) If the nodes in the lists are not lexicographically ordered, discuss how to find the intersection nodes of the two lists, and what is the corresponding time complexity.