Suffix Arrays

Suffix arrays are data structures that store all the suffixes of a given string in a sorted order. A suffix is a substring that starts from a specific index in the original string.

Suffix arrays are commonly used in string algorithms, especially for problems like pattern matching, substring queries, and sorting.

The main advantage of using a suffix array is its space efficiency compared to other data structures like suffix trees. Suffix arrays can be constructed efficiently in O(n log n) time complexity, where n is the length of the input string.

To build a suffix array for a string, we can start by creating a list of pairs, where each pair consists of a suffix and its corresponding starting index. We then sort the list of pairs based on the suffixes, and finally, extract the sorted starting indexes to form the suffix array.

Here's an example of building a suffix array in C++:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7vector<int> buildSuffixArray(string str) {
8  int n = str.size();
9  vector<int> suffixArray(n, 0);
10
11  vector<pair<string, int>> suffixes(n);
12  for (int i = 0; i < n; i++) {
13    suffixes[i] = {str.substr(i, n - i), i};
14  }
15
16  sort(suffixes.begin(), suffixes.end());
17
18  for (int i = 0; i < n; i++) {
19    suffixArray[i] = suffixes[i].second;
20  }
21
22  return suffixArray;
23}
24
25int main() {
26  string str = "banana";
27
28  vector<int> suffixArray = buildSuffixArray(str);
29
30  cout << "Suffix Array: ";
31  for (int index : suffixArray) {
32    cout << index << " ";
33  }
34  cout << endl;
35
36  return 0;
37}

The output of the above code would be:

1Suffix Array: 5 3 1 0 4 2

xxxxxxxxxx

}

#include <iostream>

#include <vector>

#include <algorithm>

​

using namespace std;

​

vector<int> buildSuffixArray(string str) {

  int n = str.size();

  vector<int> suffixArray(n, 0);

​

  vector<pair<string, int>> suffixes(n);

  for (int i = 0; i < n; i++) {

    suffixes[i] = {str.substr(i, n - i), i};

  }

​

  sort(suffixes.begin(), suffixes.end());

​

  for (int i = 0; i < n; i++) {

    suffixArray[i] = suffixes[i].second;

  }

​

  return suffixArray;

}

​

int main() {

  string str = "banana";

​

  vector<int> suffixArray = buildSuffixArray(str);

​