Hello, this a brief post about some interesting suffix array properties that are needed in some problems such as Oolimry and Suffix Array and the recently added Inverse Suffix Array problem on CSES.

Suffix array properties

Reminders:

• Given two strings $$$s$$$ and $$$t$$$, $$$s$$$ is lexicographically smaller than $$$t$$$ if and only if $$$s$$$ is a proper prefix of $$$t$$$ or there is some $$$i \lt \min(|s|,|t|)$$$ where $$$s[i] \lt t[i]$$$ and $$$s[j]=t[j]$$$ $$$\forall j$$$ such that $$$0\leq j \lt i$$$. In this case we will say $$$s \lt t$$$.
• Given a string $$$s$$$, the suffix array for $$$s$$$ is a permutation $$$p$$$ where $$$p[i]$$$ is the start of the $$$i$$$th smallest suffix of $$$s$$$ in lexicographical order.
• If $$$inv$$$ is the inverse permutation of the suffix array $$$p$$$ of $$$s$$$, then $$$inv[i] \lt inv[j]$$$ implies that $$$s[i...|s|-1] \lt s[j...|s|-1]$$$.

Basic property

If $$$s \lt t$$$ then $$$s[0]\leq t[0]$$$, otherwise we'd get that $$$s[0] \gt t[0]\implies s \gt t$$$.

By the definition of $$$p$$$, we know that $$$\forall i,j$$$ where $$$0\leq j \lt i \lt |s|:s[p[j]...n-1] \lt s[p[i]...n-1]\implies s[p[j]]\leq s[p[i]]$$$ meaning the characters at the indexes of $$$p$$$ are in non-decreasing order.

Formally, if $$$0 \lt i \lt |s|$$$ then $$$s[p[i]]\geq s[p[i-1]]$$$.

Small detour

If $$$|s|,|t|\geq 2$$$, $$$s \lt t$$$ and $$$t[1...|t|-1] \lt s[1...|s|-1]$$$ then $$$s[0] \lt t[0]$$$.

Proof: otherwise we'd get that $$$s[0]\geq t[0]$$$ but $$$s[0]\leq t[0]$$$ by basic property therefore $$$s[0]=t[0]$$$ but $$$t[1...|t|-1] \lt s[1...|s|-1]$$$ which implies that $$$t \lt s$$$ which is a contradiction.

Interesting property 1

If we have two indices $$$i,j$$$ such that $$$0\leq j \lt i \lt |s|$$$ and $$$p[i],p[j] \lt |s|-1$$$, using the third point from the reminders and the above property, we get that if $$$inv[p[j]+1] \gt inv[p[i]+1]$$$ then $$$s[p[i]] \gt s[p[j]]$$$.

Formally, if $$$0 \lt i \lt |s|$$$ and $$$p[i] \lt |s|-1$$$ then $$$s[p[i]] \gt \max\limits_{0\leq j \lt i,\text{ }p[j] \lt |s|-1,\text{ }inv[p[j]+1] \gt inv[p[i]+1]}s[p[j]]$$$.

Interesting property 2

If $$$|s|=n$$$ and $$$i \gt 0$$$ such that $$$p[i]=n-1$$$ ($$$p[i-1] \lt n-1$$$ because $$$p$$$ is a permutation of $$$0,1,...,n-1$$$), using the basic property and the definition, we get that $$$s[n-1] \gt s[p[i-1]]$$$.

Proof: otherwise we'd get that $$$s[n-1]\leq s[p[i-1]]$$$ but $$$s[n-1]\geq s[p[i-1]]$$$ by basic property therefore $$$s[n-1]=s[p[i-1]]$$$ meaning $$$s[p[i-1]...n-1]=s[n-1]+s[p[i-1]+1...n-1]\implies s[n-1]$$$ is a proper prefix of $$$s[p[i-1]...n-1]$$$ so $$$s[p[i]...n-1] \lt s[p[i-1]...n-1]$$$ which is a contradiction.

Formally, if $$$0 \lt i \lt n$$$ and $$$p[i]=n-1$$$ then $$$s[p[i]] \gt s[p[i-1]]$$$

Inverse Suffix Array

We are given the suffix array $$$p$$$ of a string $$$s$$$ which we have to reconstruct.

We will set $$$s[p[i]]$$$ to c for every $$$i=0,1,...,n-1$$$ with c being non-decreasing as $$$i$$$ increases.

c will be initialized as 'a' as it gives the most chances to increment it, and if it has to exceed 'z', then there is no valid string. Note that it's useless here to increment c by more than one letter difference at once.

When to increment c

• $$$i \gt 0$$$ and $$$p[i]=n-1$$$.
• $$$p[i] \lt n-1$$$ and there is some $$$j \lt i$$$ such that $$$p[j] \lt n-1$$$, $$$inv[p[j]+1] \gt inv[p[i]+1]$$$ and $$$s[p[j]]$$$ has current value of c.

The second part can be done using a $$$\max$$$ char Segment tree or Fenwick tree. We initialize the tree with any character that's < 'a', and then every time after setting $$$s[p[i]]$$$ to c with $$$p[i] \lt n-1$$$, we also set $$$tree[inv[p[i]+1]]$$$ to c. So that way, at any other $$$i' \gt i$$$ such that $$$p[i'] \lt n-1$$$, we can check if $$$\max(tree[inv[p[i']+1]+1...n - 1])$$$ is c meaning the second case is met so we have to increment it.