Aho Corasick 法を利用した別解です．計算量は \(O(|S|+\sum |T_i|)\) 時間です．

\(S\) の substring というのは，(\(S\) の prefix) の suffix です． そこで，\(S\) の長さ \(1, 2, \ldots\) の prefix \(P\) に対して，次を行えればよいです．

• \(T_i\) が \(P\) の suffix であるようなすべての \(i\) に対して，\(ANS[i]\) に \(1\) を加算する．

Aho Corasick 法を利用して上の問題を解きます．Aho Corasick 法については、過去に私のユーザー解説で触れたことがあるのでそちらも参照してください．

https://atcoder.jp/contests/abc268/editorial/4793

Trie を構築し，Aho Corasick 法により suffix link を計算しておきます．Trie の辺を無視して suffix link だけを考えた木を \(T\) と書くことにします．

Trie 上の辺と suffix link をたどることで，\(S\) の prefix \(P\) に対して，\(P\) の suffix に対応するような trie の頂点のうち極大なものがどこであるかが分かります． \(T\) 上でのその頂点の先祖が，\(P\) の suffix かつ trie の頂点に対応するような文字列です．よって，\(ANS[i]\) のインクリメントは，\(T\) においてある頂点から根までのパス上の頂点の値のインクリメントという操作で言い換えられます．

結局，根付き木に対してある頂点から根までのパス上の頂点に値を加算するという操作を \(O(|S|)\) 回行う問題に帰着されます．そのような操作全体の結果は，葉側からの累積和をとるという感じの木dpで \(O(|S|+|T|)\) 時間で計算できます．

解答例：https://atcoder.jp/contests/abc362/submissions/55578725