解説

dpテーブルを以下のように定義します。

• $dp[i][j] :=$長さ $i$ の文字列で、最後の $j$ 文字が、 $T$ の最初の $j$ 文字と一致しているものの個数

ただし、$j$ はできるだけ大きい値をとるようにする必要があります。

例えば、 $T=0101$ のとき、文字列 $10101$ の最後の $2$ 文字と $T$ の最初の $2$ 文字が一致しているとも考えられますが、
最後の $4$ 文字が $T$ の最初の $4$ 文字と一致していると考えます。

遷移は以下のようになります。

• $dp[i+1][j+1] += dp[i][j]$ $(S_{i+1}=T_{j+1})$
• $dp[i+1][p[j+1]] += dp[i][j]$ $(S_{i+1} \neq T_{j+1})$

ここで、 $p[j]$ は $T_1T_2...T_{k-1}=T_{j-k+1}T_{j-k+2}...T_{j-1}$ かつ $T_k \neq T_j$ を満たす最大の $k$ です。
配列$p$ を $O(|T|^2)$ で前計算した上で、dpテーブルの更新は $O(N|T|)$ で行うことができます。