題組內容

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

(a) (20%) Discuss how to find the intersection nodes of the two lists (the intersection nodes refer to the nodes appear in both of the two lists), and what is the corresponding time complexity.