advanced data structures and implementation if there is no such nodethe answer is either zero or one and is found by checking the suffix at which the search terminates this takes timeproportional to the length of the pattern pand is independent of the size of | find the most common substring of specified length return the internal node with largest size amongst those with letter depth at least this takes time ot linear-time construction of suffix arrays and suffix trees in section we showed the simplest algorithm to construct suffix array and an lcp arraybut this algorithm has on log worst-case running time for an -character string and can occur if the string has suffixes with long common prefixes in this section we describe an on worst-case time algorithm to compute the suffix array this algorithm can also be enhanced to compute the lcp array in linear timebut there is also very simple linear-time algorithm to compute the lcp array from the suffix array (see exercise and complete code in fig either waywe can thus also build suffix tree in linear time this algorithm makes use of divide and conquer the basic idea is as follows choose sampleaof suffixes sort the sample by recursion sort the remaining suffixesbby using the now-sorted sample of suffixes merge and to get an intuition of how step might worksuppose the sample of suffixes are all suffixes that start at an odd index then the remaining suffixesbare those suffixes that start at an even index so suppose we have computed the sorted set of suffixes to compute the sorted set of suffixes bwe would in effect need to sort all the suffixes that start at even indices but these suffixes each consist of single first character in an even positionfollowed by string that starts with the second characterwhich must be in an odd position thus the string that starts in the second character is exactly string that is in so to sort all the suffixes bwe can do something similar to radix sortfirst sort the strings in starting from the second character this should take linear timesince the sorted order of is already known then stably sort on the first character of the strings in thus could be sorted in linear timeafter is sorted recursively if and could then be merged in linear timewe would have linear-time algorithm the algorithm we present uses different sampling stepthat admits simple linear-time merging step as we describe the algorithmwe will also show how it computes the suffix array for the string abracadabra we adopt the following conventionss[is[ -represents the ith character of string represents the suffix of starting at index represents an array