To explain this problem, we first describe the suffix array. Given a string, the suffix array is a sequence of integers satisfying the following property:

For a string $S$, let $S[i:j]$ be its contiguous substring from the $i$-th through $j$-th characters. The suffix array of $S$ is the unique permutation $P$ of $(1,2,\dots,N)$ such that $S[P_i:N] < S[P_{i+1}:N]$ for $1 \le i \le N-1$.

The suffix array can be found in a total of \(\mathrm{O}(|S|)\) time with the SA-IS algorithm, where the size of alphabet is considered a constant.

Consider a string \(X\) obtained by concatenating the following without changing the order:

• Two copies of $S$
• $N$ copies of a
• Two copies of $T$
• $N$ copies of z

We first find the suffix array of \(X\) with the SA-IS algorithm.

Let \(g(S, i)\) be the suffix starting from the \(i\)-th character of the former \(S\), and \(g(T,j)\) be the suffix starting from the \(j\)-th character of the former \(T\).

Then, \(f(S,i) \le f(T,j) \Leftrightarrow g(S,i) \le g(T,j)\).

It can be proved because, if \(f(S,i) \neq f(T,j)\), a different character occurs in \(f(S,i)\) and \(f(T,j)\). Otherwise, noting the ordering of \(i\) and \(j\), the comparison is performed in the \(N\) copies of a and z, so \(g(S,i) \le g(T,j)\).

Using the suffix array of \(X\), we can find the number of \((i,j)\) such that \(f(S,i) \le f(T,j)\) in a total of \(\mathrm{O}(N)\) time.