A - Swap to Right

この問題は2重ループについて問います。

どの文字がどれだけ右にずらしたのかを全探索すればよいです。しかし問題は右にずらす操作です。
この操作は次の手続きを $|S|-k$ 回繰り返せば、必ず $T$ と一致する文字列を探索できます。
ここで、ずらす文字が $S$ の先頭から $k$ 番目 $S_k(=c)$ とします。

• 今いる文字 $c$ が先頭から $n\ (1\le n\le |S|-1)$ 番目であるとし、$S_n,S_{n+1}$ を入れ替える

詳細は以下の解答例をご覧ください。

また文字列が等しいかどうか判定するのに $O(N)$ だけかかることに注意すると、以上から $O(N^3)$ で解くことができます。

また別解として、区間 $[l,r]\ (1\le l\lt r\le |S|)$ に注目し、$S$ の $l$ 文字目から $r$ 文字目まで切り出した文字列 $X=S_lS_{l+1}\dots S_r$ とします。
このとき $X\ne T_lT_{l+1}\dots T_r$ を満たすのであれば $S_l$ 文字目がずらした文字であり、$K=r$ であることがわかります(逆に $X=T_lT_{l+1}\dots T_r$ ならば明らかにずらす操作は行っていないことがわかります)。

以上から $O(N)$ で解くことも可能です。