AIOJ

Some conventions

For definitions related to strings, see String Basics.

String indices start at $1$ .

The length of string $s$ is $n$ .

"Suffix $i$ " refers to the suffix beginning with the $i$ -th character. When stored, $i$ is used to represent the suffix $s[i\dots n]$ of string $s$ .

What is a suffix array?

A suffix array mainly involves two arrays: $sa$ and $rk$ .

$sa[i]$ denotes the index of the $i$ -th smallest suffix after sorting all suffixes; this is the suffix array, also called the index array $sa$ below;

$rk[i]$ denotes the rank of suffix $i$ . It is an important auxiliary array, also called the rank array $rk$ below.

These two arrays satisfy the property $sa[rk[i]]=rk[sa[i]]=i$ .

Explanation

An example of a suffix array:

How do we compute a suffix array?

The O(n^2logn) approach

This approach is probably easy to come up with: sort an array containing all suffix strings using sort. Since the sorting performs $O(n\log n)$ string comparisons and each string comparison requires $O(n)$ character comparisons, the time complexity of this sorting is $O(n^2\log n)$ .

The O(nlog^2n) approach

This approach uses the idea of doubling.

First, sort all substrings of length $1$ in string $s$ , that is, each character, obtaining the sorted index array $sa_1$ and rank array $rk_1$ .

The doubling process:

Use the ranks of two substrings of length $1$ , namely $rk_1[i]$ and $rk_1[i+1]$ , as the first and second sorting keys to sort every substring of length $2$ in string $s$ : $\{s[i\dots \min(i+1, n)]\ |\ i \in [1,\ n]\}$ , obtaining $sa_2$ and $rk_2$ ;
Then use the ranks of two substrings of length $2$ , namely $rk_2[i]$ and $rk_2[i+2]$ , as the first and second sorting keys to sort every substring of length $4$ in string $s$ : $\{s[i\dots \min(i+3, n)]\ |\ i \in [1,\ n]\}$ , obtaining $sa_4$ and $rk_4$ ;
Continue doubling in this way. Use the ranks of substrings of length $w/2$ , namely $rk_{w/2}[i]$ and $rk_{w/2}[i+w/2]$ , as the first and second sorting keys to sort every substring of length $w$ in string $s$ , $s[i\dots \min(i+w-1,\ n)]$ , obtaining $sa_w$ and $rk_w$ . As with lexicographic sorting, when $i+w>n$ , treat $rk_w[i+w]$ as negative infinity;
$rk_w[i]$ is the rank of substring $s[i\dots i + w - 1]$ . Thus, when $w \geqslant n$ , the resulting index array $sa_w$ is the suffix array we need.

Process

Illustration of the doubling sort:

Clearly, the doubling process takes $O(\log n)$ iterations, and sorting the substrings with sort in each iteration takes $O(n\log n)$ ; each substring comparison costs $2$ character comparisons.

In addition, after each sort, updating $rk$ takes an extra $O(n)$ time, but this is negligible compared with $O(n\log n)$ .

Therefore, the time complexity of this algorithm is $O(n\log^2n)$ .

Implementation

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

constexpr int N = 1000010;

char s[N];
int n, w, sa[N], rk[N << 1], oldrk[N << 1];

// Allocate an array twice as large to prevent out-of-bounds access when accessing rk[i+w].
// Of course, one can also check for out-of-bounds access before accessing it, but simply using an array twice as large is more convenient.

int main() {
  int i, p;

  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (i = 1; i <= n; ++i) sa[i] = i, rk[i] = s[i];

  for (w = 1; w < n; w <<= 1) {
    sort(sa + 1, sa + n + 1, [](int x, int y) {
      return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];
    });  // A lambda is used here
    memcpy(oldrk, rk, sizeof(rk));
    // Since the original rk will be overwritten while computing rk, copy it first.
    // If two substrings are equal, their corresponding rk values must also be equal, so duplicates must be removed.
    for (p = 0, i = 1; i <= n; ++i) {
      if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
          oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) {
        rk[sa[i]] = p;
      } else {
        rk[sa[i]] = ++p;
      }
    }
  }

  for (i = 1; i <= n; ++i) printf("%d ", sa[i]);

  return 0;
}

The O(nlogn) approach

In the $O(n\log^2n)$ approach just described, each sort takes $O(n\log n)$ . If we can sort in $O(n)$ , we can compute the suffix array in $O(n\log n)$ .

Prerequisites: Counting Sort, Radix Sort.

During suffix-array computation, the sorting keys are ranks, whose value range is $O(n)$ , and the sort has two keys. Thus, radix sort can optimize it to $O(n)$ .

Implementation

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

constexpr int N = 1000010;

char s[N];
int n, sa[N], rk[N << 1], oldrk[N << 1], id[N], cnt[N];

int main() {
  int i, m, p, w;

  scanf("%s", s + 1);
  n = strlen(s + 1);
  m = 127;
  for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
  memcpy(oldrk + 1, rk + 1, n * sizeof(int));
  for (p = 0, i = 1; i <= n; ++i) {
    if (oldrk[sa[i]] == oldrk[sa[i - 1]]) {
      rk[sa[i]] = p;
    } else {
      rk[sa[i]] = ++p;
    }
  }

  for (w = 1; w < n; w <<= 1, m = n) {
    // Counting-sort the second key: id[i] + w
    memset(cnt, 0, sizeof(cnt));
    memcpy(id + 1, sa + 1,
           n * sizeof(int));  // id stores a copy of sa, essentially serving as oldsa
    for (i = 1; i <= n; ++i) ++cnt[rk[id[i] + w]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[id[i] + w]]--] = id[i];

    // Counting-sort the first key: id[i]
    memset(cnt, 0, sizeof(cnt));
    memcpy(id + 1, sa + 1, n * sizeof(int));
    for (i = 1; i <= n; ++i) ++cnt[rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[id[i]]]--] = id[i];

    memcpy(oldrk + 1, rk + 1, n * sizeof(int));
    for (p = 0, i = 1; i <= n; ++i) {
      if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
          oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) {
        rk[sa[i]] = p;
      } else {
        rk[sa[i]] = ++p;
      }
    }
  }

  for (i = 1; i <= n; ++i) printf("%d ", sa[i]);

  return 0;
}

Some constant-factor optimizations

If you submit the code above to LOJ #111: Suffix Sorting:

This is because the constants of the code above are indeed quite large.

The second key does not need counting sort

Consider the essence of sorting by the second key. It is simply to put the $sa[i]$ whose range exceeds the string (that is, $sa[i] + w > n$ ) at the head of the $sa$ array, then put the rest in their original order:

int cur = 0;
for (int i = n - w + 1; i <= n; i++) id[++cur] = i;
for (int i = 1; i <= n; i++)
  if (sa[i] > w) id[++cur] = sa[i] - w;

Optimize the value range of counting sort

After updating $rk$ each time, we calculate a $p$ . This $p$ is exactly the value range of $rk$ , so we can use it as the value range.

If all ranks are distinct, the suffix array can be generated directly

Consider the new $rk$ array. If its value range is $[1,n]$ , then every rank is different, so no further sorting is needed.

Implementation

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

constexpr int N = 1000010;

char s[N];
int n;
int m, p, rk[N * 2], oldrk[N], sa[N * 2], id[N], cnt[N];

int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  m = 128;

  for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
  for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;

  for (int w = 1;; w <<= 1, m = p) {  // m = p is the value-range optimization
    int cur = 0;
    for (int i = n - w + 1; i <= n; i++) id[++cur] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > w) id[++cur] = sa[i] - w;

    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) cnt[rk[i]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];

    p = 0;
    memcpy(oldrk, rk, sizeof(oldrk));
    for (int i = 1; i <= n; i++) {
      if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
          oldrk[sa[i] + w] == oldrk[sa[i - 1] + w])
        rk[sa[i]] = p;
      else
        rk[sa[i]] = ++p;
    }

    if (p == n) break;  // No further sorting is needed when p = n
  }

  for (int i = 1; i <= n; i++) printf("%d ", sa[i]);

  return 0;
}

The O(n) approach

For general problems, the doubling method for suffix arrays, with its small constants, is entirely sufficient. The parts other than suffix-array computation also often have $O(n\log n)$ complexity, so doubling will not become the bottleneck.

However, for special problems, problems with tight time limits, or when you want to pursue shorter runtimes, you need to learn an $O(n)$ method for computing suffix arrays.

SA-IS

See Induced Sorting and the SA-IS Algorithm; its comments page is also useful.

DC3

See [2009] Suffix Arrays—A Powerful Tool for Processing Strings by Luo Suiqian.

Applications of suffix arrays

Finding the position of the smallest cyclic shift

Duplicating string $S$ to form $SS$ turns this into a suffix-sorting problem.

Example problem: 「JSOI2007」Character Encryption.

Finding a substring in a string

The task is to find a pattern string $S$ online in a text string $T$ . Online means that we know the text string $T$ in advance, but learn the pattern string $S$ only when a query is made. We can first construct the suffix array of $T$ , then search for substring $S$ . If substring $S$ occurs in $T$ , it must be a prefix of some suffixes of $T$ . Since all suffixes have already been sorted, we can find $S$ by binary-searching in the $p$ array. Comparing substring $S$ with the current suffix takes $O(|S|)$ time, so finding the substring takes $O(|S|\log |T|)$ time. Note that if the substring occurs multiple times in $T$ , all occurrences are adjacent in the $p$ array. Thus, the number of occurrences can be found with another binary search, and outputting every occurrence position is also easy.

Minimizing lexicographic order by taking characters from either end

Example problem: 「USACO07DEC」Best Cow Line.

Problem statement: Given a string, take one character from either the beginning or the end at each step to form a string. Find the lexicographically smallest string that can be formed.

Solution

The brute-force approach checks at each step, in the worst case in $O(n)$ time, whether to take the first or last character (that is, comparing the string obtained by taking the first character with the reverse of the string obtained by taking the last character). It is enough to optimize this decision process.

Since we need to compare suffixes of the original string with suffixes of its reverse, concatenate the reverse to the original string and insert a character not appearing in either string in the middle (such as #; the code can directly use the null character). Computing the suffix array then lets us make this comparison in $O(1)$ time.

Reference code

#include <cctype>
#include <cstring>
#include <iostream>
using namespace std;

constexpr int N = 1000010;

char s[N];
int n, sa[N], id[N], oldrk[N * 2], rk[N * 2], px[N], cnt[N];

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  int i, w, m = 200, p, l = 1, r, tot = 0;

  cin >> n;
  r = n;

  for (i = 1; i <= n; ++i)
    while (cin >> s[i], !isalpha(s[i]));
  for (i = 1; i <= n; ++i)
    rk[i] = rk[2 * n + 2 - i] = s[i];  // Concatenate the original and reversed strings, leaving one character unused in the middle

  n = 2 * n + 1;
  // Compute the suffix array
  for (i = 1; i <= n; ++i) ++cnt[rk[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w *= 2, m = p) {  // m=p is the optimization of the counting-sort value range
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  // Use the suffix array to make the comparison in O(1) time
  while (l <= r) {
    cout << (rk[l] < rk[n + 1 - r] ? s[l++] : s[r--]);
    if ((++tot) % 80 == 0) cout << '\n';  // Newline
  }

  return 0;
}

The height array

LCP (longest common prefix)

The LCP of two strings $S$ and $T$ is the largest $x$ ( $x\le \min(|S|, |T|)$ ) such that $S_i=T_i\ (\forall\ 1\le i\le x)$ .

Below, $lcp(i,j)$ denotes the longest common prefix (length) of suffixes $i$ and $j$ .

Definition of the height array

$height[i]=lcp(sa[i],sa[i-1])$ , that is, the longest common prefix of the suffix ranked $i$ and the suffix ranked immediately before it.

$height[1]$ can be regarded as $0$ .

O(n) A lemma needed to compute the height array

$height[rk[i]]\ge height[rk[i-1]]-1$

Proof

When $height[rk[i-1]]\le1$ , the inequality is obvious (the right-hand side is at most $0$ ).

When $height[rk[i-1]]>1$ :

By the definition of $height$ , $lcp(sa[rk[i-1]], sa[rk[i-1]-1]) = height[rk[i-1]] > 1$ .

Since suffix $i-1$ and suffix $sa[rk[i-1]-1]$ have a longest common prefix of length $height[rk[i-1]]$ ,

let us denote this longest common prefix by $aA$ . (Here $a$ is a character, and $A$ is a nonempty string of length $height[rk[i-1]]-1$ .)

Then suffix $i-1$ can be written as $aAD$ , and suffix $sa[rk[i-1]-1]$ can be written as $aAB$ . ( $B < D$ ; $B$ may be an empty string, while $D$ is nonempty.)

Furthermore, suffix $i$ can be written as $AD$ , and suffix $sa[rk[i-1]-1]+1$ exists and is $AB$ .

Since suffix $sa[rk[i]-1]$ is only one position below suffix $sa[rk[i]]$ , which is suffix $i$ , in rank order, and $AB < AD$ ,

we have $AB \leqslant$ suffix $sa[rk[i]-1] < AD$ . Clearly, suffix $i$ and suffix $sa[rk[i]-1]$ share the prefix $A$ .

Therefore, $lcp(i,sa[rk[i]-1])$ is at least $height[rk[i-1]]-1$ , which gives $height[rk[i]]\ge height[rk[i-1]]-1$ .

O(n) Implementation of the height array computation

The lemma above lets us compute it by brute force:

for (i = 1, k = 0; i <= n; ++i) {
  if (rk[i] == 0) continue;
  if (k) --k;
  while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
  height[rk[i]] = k;
}

$k$ never exceeds $n$ and is decremented at most $n$ times, so it is incremented at most $2n$ times in total. The overall complexity is $O(n)$ .

Applications of the height array

Longest common prefix of two substrings

$lcp(sa[i],sa[j])=\min\{height[i+1..j]\}$

Intuitively, if $height$ is always greater than some value, those many initial characters have never changed; conversely, since the suffixes are already sorted, they cannot change and then change back.

For a rigorous proof, see [2004] Suffix Array by Xu Zhilei.

With this theorem, finding the longest common prefix of two substrings becomes an RMQ problem.

Comparing the order of two substrings of a string

Suppose we need to compare $A=S[a..b]$ and $B=S[c..d]$ .

If $lcp(a, c)\ge\min(|A|, |B|)$ , $A [!note]- Solution

A string occurring at least $k$ times means that, after suffix sorting, at least $k$ consecutive suffixes have this substring as a common prefix.

Therefore, find the minimum of every consecutive $k-1$ values of $height$ , then the maximum of these minima is the answer.

A monotonic queue can solve this in $O(n)$ , but other methods are also sufficient to get AC.

Reference code

#include <cstring>
#include <iostream>
#include <set>

using namespace std;

constexpr int N = 40010;

int n, k, a[N], sa[N], rk[N], oldrk[N], id[N], px[N], cnt[1000010], ht[N], ans;
multiset<int> t;  // multiset is the easiest implementation to write

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int i, j, w, p, m = 1000000;

  cin >> n >> k;
  --k;

  for (i = 1; i <= n; ++i) cin >> a[i];  // Compute the suffix array
  for (i = 1; i <= n; ++i) ++cnt[rk[i] = a[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w <<= 1, m = p) {
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }

  for (i = 1, j = 0; i <= n; ++i) {  // Compute height
    if (j) --j;
    while (a[i + j] == a[sa[rk[i] - 1] + j]) ++j;
    ht[rk[i]] = j;
  }

  for (i = 1; i <= n; ++i) {  // Find the maximum of all minima
    t.insert(ht[i]);
    if (i > k) t.erase(t.find(ht[i - k]));
    ans = max(ans, *t.begin());
  }

  cout << ans;

  return 0;
}

Whether some string occurs at least twice without overlapping in the text

We can binary-search the length $|s|$ of the target string, divide the $h$ array into several consecutive segments whose LCP is at least $|s|$ , and use RMQ on each segment to find the maximum and minimum indices among the occurrences. If the distance between these two indices meets the condition, then there must be a string of length $|s|$ that occurs twice without overlapping.

Several consecutive equal substrings

We can enumerate the length $|s|$ of the repeated string, divide the entire string into blocks of length $|s|$ , and query the LCP and LCS of the beginnings of adjacent blocks. See [2009] Suffix Arrays—A Powerful Tool for Processing Strings for details.

Example problem: 「NOI2016」Excellent Split.

Combining with a disjoint-set union

Some problems require dividing the suffix array into several consecutive segments whose LCP length is at least a given value; equivalently, divide the $h$ array into consecutive segments whose minimum is at least a given value and compute the answer for each segment. If there are multiple queries, we can process them offline. Observe that as the given value decreases monotonically, the number of intervals satisfying the condition keeps decreasing, while each new interval is formed by joining two or more original intervals, and the parts of a new interval that were not contained in an original interval all have $h$ value equal to the newly decreased value. We only need to maintain a disjoint-set union, merging adjacent intervals each time and maintaining the aggregate information.

Classic problem: 「NOI2015」Wine Tasting Conference

Combining with a segment tree

Some problems ask for the first several numbers satisfying a condition, and these numbers all lie within an interval in suffix order. We can then use the merge-sort property to merge information from two nodes, and use a segment tree to maintain and query the answer for an interval.

Combining with a monotonic stack

Example problem: 「AHOI2013」Difference

Solution

The first two terms of the addends are easy to handle: $n(n-1)(n+1)/2$ (each suffix appears $n-1$ times, and the total suffix length is $n(n+1)/2$ ). The key is the last term, namely the pairwise LCP of suffixes.

We know that $lcp(i,j)=k$ is equivalent to $\min\{height[i+1..j]\}=k$ . Therefore, we can regard $lcp(i,j)$ as the contribution to the answer of $\min\{x|i+1\le x\le j, height[x]=lcp(i,j)\}$ .

Consider which suffix LCPs each position contributes to. It is equivalent to choosing one suffix from the consecutive suffixes to its left whose $height$ values are greater than it, and one suffix from the consecutive suffixes to its right whose $height$ values are no less than it. This can be computed with a monotonic stack.

The monotonic-stack part is similar to Luogu P2659 Beautiful Sequence and the horizontal scanning method.

Reference code

#include <cstring>
#include <iostream>
#include <string>
using namespace std;

constexpr int N = 500010;

string s;
int n, sa[N], rk[N << 1], oldrk[N << 1], id[N], px[N], cnt[N], ht[N], sta[N],
    top, l[N];
long long ans;

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  int i, k, w, p, m = 300;

  cin >> s;
  n = s.size();
  s = " " + s;
  ans = 1ll * n * (n - 1) * (n + 1) / 2;
  // Compute the suffix array
  for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w <<= 1, m = p) {
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  // Compute height
  for (i = 1, k = 0; i <= n; ++i) {
    if (k) --k;
    while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
    ht[rk[i]] = k;
  }
  // Maintain the monotonic stack
  for (i = 1; i <= n; ++i) {
    while (ht[sta[top]] > ht[i]) --top;  // top is similar to a pointer
    l[i] = i - sta[top];
    sta[++top] = i;
  }
  // Finally, use the monotonic stack to calculate ans
  sta[++top] = n + 1;
  ht[n + 1] = -1;
  for (i = n; i >= 1; --i) {
    while (ht[sta[top]] >= ht[i]) --top;
    ans -= 2ll * ht[i] * l[i] * (sta[top] - i);
    sta[++top] = i;
  }

  cout << ans;

  return 0;
}

A similar problem: 「HAOI2016」Finding Equal Characters.

Exercises

References

This page (the part introduced by 4070a9b) is mainly translated from the blog post Суффиксный массив and its English translation, Suffix Array. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.

Papers:

Introduction to Suffix Arrays

Some conventions

What is a suffix array?

Explanation

How do we compute a suffix array?

The O(n^2logn) approach

The O(nlog^2n) approach

Process

The O(nlogn) approach

Some constant-factor optimizations

The second key does not need counting sort

Optimize the value range of counting sort

If all ranks are distinct, the suffix array can be generated directly

The O(n) approach

SA-IS

DC3

Applications of suffix arrays

Finding the position of the smallest cyclic shift

Finding a substring in a string

Minimizing lexicographic order by taking characters from either end

The height array

LCP (longest common prefix)

Definition of the height array

O(n) A lemma needed to compute the height array

O(n) Implementation of the height array computation

Applications of the height array

Longest common prefix of two substrings

Comparing the order of two substrings of a string

Whether some string occurs at least twice without overlapping in the text

Several consecutive equal substrings

Combining with a disjoint-set union

Combining with a segment tree

Combining with a monotonic stack

Exercises

References