公式解説のステップ2はもう少し簡単にできます。

公式解説で述べられている「\(T_i\)​ と一致するような接尾辞を表すSA上の区間」を探すのは、同じ箇所を2度調べないようにした線形探索で十分です。（\(T_i\) の文字列長昇順で行うと、「今までに見た区間に完全に内包される」「今までに見た区間とはdisjoint」のどちらかしか起こらないので）

以下実装上の工夫を述べます。

\(S,T_i\) に含まれる全ての文字より小さい文字(ここでは @)と、大きい文字(ここでは ~)を用意し、\(X:=T_1+\) @ \(+T_2+\ldots+T_N+\) @ \(+S+\) ~ という文字列に対するSuffix Array及びLCP Arrayを構築します。
このとき、\(X\) の Suffix \(T_i+\) @ \(+\ldots\) に注目すると、これは、\(T_i\) をPrefixに持つような \(S+\) ~ のSuffix の全てより辞書順で小さいことがわかります。したがって、\(T_i\) をPrefixに持つような \(S\) の Suffix は、Suffix Array上でこの後ろを探せば十分です。(区切り文字をこのようにしない場合、前後両方を探索する必要があります)

これを \(|T_i|\) の小さい順に行い、一度見たSuffixにはフラグをつけ、2度見ないようにすることで、\(O(|X|)\) 時間でステップ2を行うことができます。