「\(S\) を部分文字列として \(K\) 箇所含む文字列のうち最短のもの」を \(T_K\) とします。

\(T_2\) は「先頭から \(N\) 文字が \(S\) かつ、末尾から \(N\) 文字が \(S\)」となります。（もしそうでないなら、先頭または末尾の文字を削除しても、\(S\) を部分文字列として含む個数が変化しないため、最小性に反します）

 　┌───┐     
abcabcab
└───┘

「先頭から \(N\) 文字が \(S\) かつ、末尾から \(N\) 文字が \(S\)」となる文字列の中で長さが最小となるのは、2個所の \(S\) の重なりが最も大きいときなので、その長さは \(S\) の prefix と \(S\) の suffix が一致する最大の文字数を \(m\) として \(2N-m\) となります。これは Z-algorithm を用いることで、\(O(N)\) で求めることができます。

一般の場合を考えます。「\(T\) の中で \(i\) 番目に登場する \(i+1\) 番目に登場する \(S\) を含む最小の部分列」が \(T_2\) と一致しない場合、この部分を \(T_2\) に置き換えることでより短い列を得ることができます。（置き換える前後で先頭 \(N\) 文字と末尾 \(N\) 文字は変化しないため、\(S\) を含む他の箇所には影響しません）

 　┌───┐ ┌───┐
abcabcabcabcab
└───┘ └───┘

よって一般の場合も最も重なりが大きくなるように貪欲につなげるのが最適であり、求める長さは \(KN-(K-1)m\) となります。