\(L=|S|,M=\sum_i|T_i|\) とします。ローリングハッシュを使った \(O(L\sqrt{M\log N})\) 解法を述べます。高速なhashを用いることで実行時間制限に間に合わせることができます。

参考：安全で爆速なRollingHashの話 (keymoonさんによる記事)

空文字列 \(X\) から始めて、\(S\) の文字を先頭から順に1文字ずつ \(X\) の末尾に追加していくことを考えます。各文字を追加した直後、\(X\) のsuffixが \(T\) のいずれかと一致している場合、\(X\) の末尾を * に置換するのが最適です。

これを愚直に行うと、全体で \(\Omega(LM)\) の時間がかかります。そこで、各 \(T\) が \(X\) のsuffixであるかどうかをローリングハッシュを用いてチェックすることにします。これでもまだ \(\Omega(LN)\) かかるように見えますが、「\(T\) のうち長さが \(W\) であるような文字列のhashからなるset」を各 \(W\) について持っておけば、文字列長の種類数は \(O(\sqrt{M})\)であることから、全体で \(O(L\sqrt{M}\log N)\) 時間で処理できます。

実装例(C++) ※ \(S\) の先頭からではなく末尾から順に処理しています

この解法は実装を適切に工夫することで \(O(L\sqrt{M\log N})\) になります。