Strings are a stark data structure, universal and portable representation of all information that allows

random access to the linear text stored within. Under the hood, strings are character arrays,

but the primitive nature of such arrays is hidden behind a higher abstraction interface of the public

methods of String class. Surprising algorithms have been developed over the years to quickly

search and analyze both the string itself and the semantic information encoded in it$.$ Even the seemingly

simple task of searching for a pattern inside the given text can be optimized in countless ways,

let alone various higher level tasks performed on these string instruments.

Occasionally the string data structure can be augmented with additional data that speeds up operations

that would be inefficient if we were given only the raw unadorned text string itself. Even

though this data in principle adds nothing new to the mix in that its contents are fully determined

by the contents of the original string, having that redundant information available in a different

form can provide significant speedups, as yet another form of the classic space$-$time tradeoff. This

lab showcases a simple but powerful suffix array method as a technique to preprocess any text so

that after the metaphorical cheque for the one$-$time payment of this preprocessing has cleared, all

future searches of arbitrary patterns can be executed in time that grows only logarithmically with

respect to the length of the text. This makes these pattern searches blazingly fast even if performed

on the entire War and Peace!

Computed from the given text string that has n characters, its suffix array is an n$-$element array of

integers that contains the position indices $0,...,$ n $1$ into the text. Since each position is stored in

the suffix array exactly once, the suffix array is some permutation of order n$.$ The suffix array lists

these n positions sorted in the lexicographic order $($also called the $$dictionary order$)$ of the