\(t\) を空文字列とします。 以下の処理を \(s\) が空になるまで繰り返せばよいです。

• \(s\) の先頭の文字を取り除き、\(t\) の末尾に追加する。その後、\(t\) の末尾 \(3\) 文字が fox ならば、\(t\) の末尾 \(3\) 文字を取りのぞく。

これは \(O(N)\) で動作し、十分高速です。