\(i, j\) が与えられたときに \(f(S, i) \leq f(T, j)\) かどうかを判定するクエリを考えます。これは、\(f(S, i)\) と \(f(T, j)\) の先頭から何文字目までが一致しているかを求めて、はじめて一致しなくなる文字を比較すればよいです。一般に、文字列の二つの suffix の先頭から何文字目までが一致しているかという値は、LCP Array の区間最小値に対応します（詳細略）。よって、\(S + S + T + T\) の Suffix Array と LCP Array を求めて、LCP Array の区間最小値をセグメント木で処理することで、前計算 \(O(N)\)、クエリ \(O(\log N)\) で処理できます（区間最小値を処理するデータ構造によって計算量が変わります。たとえば Sparse Table を用いた場合、前計算 \(O(N \log N)\)、クエリ \(O(1)\) になります。他にも、前計算 \(O(N)\)、クエリ \(O(1)\) で行う方法もあります）。

あとは、\(j = 0, 1, \ldots, N - 1\) を \(f(T, j)\) の昇順に並べた順列を作り（これは \(T + T\) の Suffix Array から求まります）、各 \(i\) について \(f(S, i) \leq f(T, j)\) を満たす \(j\) の範囲を二分探索で求めることで、この問題を解くことができます。全体計算量は \(O(N (\log N)^2)\) や \(O(N \log N)\) になります。

実装例（C++ with AtCoder Library）