Question

Let S be a string that ends with a distinct end symbol S. In the suffix tree for S, each edge is labeled by a substring of S. For any node u, we use path(u) to denote the string formed by concatenating the labels of the edges along the path from root to u. For instance, path(root), the empty string. And for any leaf ls a suffix of S in the suffix tree, path(e) For two internal nodes u and v in the suffix tree, if path(u) can be formed by removing the first character of path(v), then, u is called a suffir link of v, and we may indicate this relationship by drawing a dotted arrow from e to u (a) (20%) Draw the suffix tree of the string ababaas. and indicate clearly all the suffix links in the tree. (b) (15%) Show that for each non-root internal node, its suffix link must exist.

Answer 1

1.

o a เก

2. As per the diagram above for every non internal non root node - a parent exists ($) link exist - the trailing node (str(len) - 1) contains the ($).