（公式解説の動画を見る前に書いたので、公式解説での KMP 法による解法と被ってしまっています）

\(T\) の末尾から 1 文字以上の文字列を取り除くという操作を行っても、この問題の答え（\(T\) を作るのに必要な \(S\) の接頭辞の最小個数）は増加しません。なぜなら、元の最小個数を実現する接頭辞の組を考え、後方の接頭辞から順に短くしていくことで、短くした \(T\) に対する答えを構成することができるためです。

このことに注意すると、次のアルゴリズムにより \(k\) を求められることがわかります。

1. \(T\) が空でない限り、\(T\) の接尾辞であって、\(S\) の接頭辞になっているもののうち最長のものを \(T\) の末尾から取り除く。そのような接尾辞として空文字列しか存在しない場合は不可能。
2. 1 で接尾辞を取り除いた回数を \(k\) とする。

正当性は、最初の議論から、1. の各ステップで最長の接尾辞を取り除くことが常に最も有利であることがわかることから従います。

さらに、KMP 法 を用いると、\(T\) の各接頭辞に対し、「\(S\) の接頭辞であるような最長の接尾辞の長さ」を \(O(|S| + |T|)\) で求めることができます。これを使うと先程のアルゴリズムの 1. を効率よく行うことができ、全体として \(O(|S| + |T|)\) で答えを求めることができます。