Consider the following descending suffix walk by string S = s1s2 · · · sm on the suffix trie of T = t1t2 · · · tn. Walk down the suffix tree of T as deep as the prefix of S still matches the path...

Consider the following descending suffix walk by string S = s1s2 · · · sm on the suffix trie of T = t1t2 · · · tn. Walk down the suffix tree of T as deep as the prefix of S still matches the path followed. When you cannot walk any more, say at si, follow a suffix link, and continue walking down as deep as the prefix of sisi+1 · · · still matches the path followed, and follow another suffix link when needed. Continue this until you reach the end of S. Observe that the node v visited during the walk whose string depth is greatest defines the longest common substring of S and T: the string X labeling the path from root to v is such a substring. Now, consider the same algorithm on the suffix tree of T. Use the simulation of implicit suffix links from the previous assignment. Show that the running time is O(s + |T| + |S|log s), i.e. the time spent in total for simulating implicit suffix links can be amortized on scanning S.