advanced data structures and implementation assuming that the size of is less than (and usually it is significantly less)then we would reasonably expect that the time to solve this problem for given and would be at least linear in the length of tand in fact there are several ot algorithms howeverwe are interested in more common problemin which is fixedand queries with different occur frequently for instancet could be huge archive of email messagesand we are interested in repeatedly searching the email messages for different patterns in this casewe are willing to preprocess into nice form that would make each individual search much more efficienttaking time significantly less than linear in the size of --either logarithmic in the size of tor even betterindependent of and dependent only on the length of one such data structure is the suffix array and suffix tree (that sounds like two data structuresbut as we will seethey are basically equivalentand trade time for spacesuffix arrays suffix array for texttis simply an array of all suffixes of arranged in sorted order for instancesuppose our text string is banana then the suffix array for banana is shown in figure suffix array that stores the suffixes explicitly would seem to require quadratic spacesince it stores one string of each length to (where is the length of tin ++this is not exactly truesince in +we can use the primitive null-terminated array of character representation of stringsand in that casea suffix is specified by char that points at the first character of the substring thusthe same array of characters is sharedand the additional memory requirement is only the char pointer for the new substring nonethelessusing char is highly or +dependentthus it is common for practical implementation to store only the starting indices of the suffixes in the suffix arraywhich is much more language independent figure shows the indices that would be stored the suffix array by itself is extremely powerful for instanceif patternpoccurs in the textthen it must be prefix of some suffix binary search of the suffix array would be enough to determine if the pattern is in the textthe binary search either lands on por would be between two valuesone smaller than and one larger than if is prefix of some substringit is prefix of the larger value found at the end of the binary search immediatelythis reduces the query time to op log )where the log is the binary searchand the is the cost of the comparison at each step ana anana banana na nana figure suffixes for "banana