node with letter depth of is representing the common string "anain all nodes that are below it and the internal node with letter depth of is representing the common string "nain all nodes that are below it in factthis analysis makes clear that suffix tree is equivalent to suffix array plus an lcp array if we have suffix treewe can compute the suffix array and the lcp array by performing an inorder traversal of the tree (compare figure with the suffix tree in figure at that time we can compute the lcp as followsif the suffix node value plus the letter depth of the parent is equal to nthen use the letter depth of the grandparent as the lcpotherwise use the parent' letter depth as the lcp in figure if we proceed inorderwe obtain for our suffixes and lcp values suffix with lcp (the grandparentbecause equals suffix with lcp (the grandparentbecause equals suffix with lcp (the parentbecause does not equal suffix with lcp (the parentbecause does not equal suffix with lcp (the grandparentbecause equals suffix with lcp (the parentbecause does not equal this transformation can clearly be done in linear time the suffix array and lcp array also uniquely define the suffix tree firstcreate root with letter depth then search the lcp array (ignoring position for which lcp is not really definedfor all occurrences of the minimum (which at this phase will be the zerosonce these minimums are foundthey will partition the array (view the lcp as residing between adjacent elementsfor instancein our examplethere are two zeros in the lcp arraywhich partitions the suffix array into three portionsone portion containing the suffixes { }another portion containing the suffix { }and the third portion containing the suffixes { the internal nodes for these portions can be built recursivelyand then the suffix leaves can be attached with an inorder traversal although it is not obviouswith care the suffix tree can be generated in linear time from the suffix array and lcp array the suffix tree solves many problems efficientlyespecially if we augment each internal node to also maintain the number of suffixes stored below it small sampling of suffix tree applications includes the following find the longest repeated substring in ttraverse the treefinding the internal node with the largest number letter depththis represents the maximum lcp the running time is ot this generalizes to the longest substring repeated at least times find the longest common substring in two strings and form string # where is character that is not in either string then build suffix tree for the resulting string and find the deepest internal node that has at least one suffix that starts prior to the #and one that starts after the this can be done in time proportional to the total size of the strings and generalizes to an ok algorithm for strings of total length find the number of occurrences of the pattern passuming that the suffix tree is augmented so that each node keeps track of the number of suffixes below itsimply follow the path down the treethe first internal node that is prefix of provides the answer