\(dp[i] =\) (相異なっても良い) \(S\) の接頭辞を \(k\) 個連結することで \(T\) の \(1\) 文字目から \(i\) 文字目までを取り出した文字列 \(T'\) と一致させられるような最小の非負整数 \(k\)

とします。はじめ、

\( dp[i] =\left\{ \begin{array}{l} 0 & (i = 0) \\ ∞ & (i>0) \end{array} \right. \) です。

求めたいものは \(dp[|T|]\) です。

配るdpでこのdpテーブルを更新していくことを考えると、\(i\) の小さいほうから以下のように更新することが出来ます。

• \(T\) の \(i+1\) 文字目以降の \(l\) 文字と、 \(S\) の先頭からの \(l\) 文字が一致するような最大の非負整数 \(l\) を求める。
• 各 \(j=i+1,i+2,\ldots,i+l\) について、 \(dp[j]\) を \(\min(dp[j],dp[i]+1)\) で更新する。
  

愚直に処理すると間に合わないので、高速に処理する方法を考えます。

前者の処理は例えばローリングハッシュを用いて二分探索を行うことにより \(O(\log \min(|S|,|T|))\) で行えるので、全体で \(O(|T| \log \min(|S|,|T|))\) で処理できます。
後者の処理は例えばSegment Tree Beatsの区間chminクエリで処理することによって全体で \(O(|T| \log |T|)\) で処理できます。(こちらはならし計算量です)

よって、入出力なども合わせた全体での計算量は \(O(|S|+|T| \log |T|)\) となり、実行時間制限に間に合わせることが出来ます。