Let \(dp[i]\) be the answer for the first \(i\) characters of \(T\) (and \(\infty\) for no answer). If \(P_i\) is the set of lengths \(p\) where the \(T_{i-p+1 .. i} = S_{1..p}\), then \(dp[i] = \min_{p \in P_i} dp[i-p] + 1\)

It can be shown that \(dp[i] \leq dp[i+1]\) for all \(0 \leq i \leq |T|-1\). That’s because for any solution for \(T\)-prefix \(i+1\), we can delete the last character of the last \(S\)-prefix (and then delete that prefix if it’s empty), and therefore \(dp[i] \leq dp[i+1]\) or \(dp[i+1] - 1\). Therefore we only care about values \(p_i = \max P_i\), i.e. the maximum length of an \(S\)-prefix that is a suffix of \(T_{1..i}\).

These values can be found by finding the prefix function (a.k.a. Knuth-Morris-Pratt / KMP) of the string \(S + \# + T\) (where \(\#\) represents a unique sentinel character that isn’t already in either string) then dropping the first \(|S| + 1\) elements. Note the answer is nullity if any \(p_i = 0\).

Therefore the problem has been solved in \(O(|S| + |T|)\) time.