cout << "String to be sorted: ";
cin >> wordToSort;
cout << "Sorted suffixes of " << wordToSort << endl;
for(int index = 0; index < SIZE; index++)
suffix[index] = wordToSort.substr(index, SIZE);
A suffix of a string s is a substring of s that ends with the last character of s.
For example, if s is the string potato, then the suffixes of s are potato, otato, tato, ato, to, and o.
(Technically the empty string can be considered a suffix, but we'll ignore that case.) Observe that the
number of suffixes of s is exactly equal to the length of s. We can number the suffixes and say that
the ith sux of s is the one that begins with the ith letter of s. We can represent all of the suffixes
of a string s by storing the string in a character array and then constructing an array of pointers that
point to the appropriate character in the string. For example, if suffix is our array of pointers then
suffix will point to the rest o in the character array containing potato.
Write a program that reads in a string (of maximum length 100000), constructs the suffix
array pointing to the appropriate character in the string, sorts the suffixes, and then displays them in
their sorted order. You must use the QuickSort algorithm, which you will need to modify to handle your
array of pointers. You may not make copies of the string or parts of the string in your code. You should
only need two 1D arrays: one for the string you read in and one to represent the suffixes. The suffix
array should be declared as an array of char pointers:
This assignment requires very little new code to be written. You will have to modify QuickSort so that
it sorts an array of character pointers. Constructing the sux array takes only a few lines of code, as
does displaying it. But you do need a good understanding of pointers and how they work.