AT_abc272_f [ABC272F] Two Strings

[problemUrl]: https://atcoder.jp/contests/abc272/tasks/abc272_f 長さ $ N $ の英小文字からなる文字列 $ S,T $ が与えられます。 文字列 $ X $ と整数 $ i $ に対し、$ f(X,i) $ を $ X $ に対して以下の操作を $ i $ 回行い得られる文字列とします。 - $ X $ の先頭の文字を削除し、同じ文字を $ X $ の末尾に挿入する。 $ 0\ \le\ i,j\ \le\ N-1 $ を満たす非負整数の組 $ (i,j) $ のうち、辞書順で $ f(S,i) $ が $ f(T,j) $ より小さいか同じであるものの個数を求めてください。 辞書順とは？ 辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 $ S,\ T $ の大小を判定するアルゴリズムを以下に説明します。 以下では「 $ S $ の $ i $ 文字目の文字」を $ S_i $ のように表します。また、 $ S $ が $ T $ より辞書順で小さい場合は $ S\ \lt\ T $ 、大きい場合は $ S\ \gt\ T $ と表します。 1. $ S,\ T $ のうち長さが大きくない方の文字列の長さを $ L $ とします。$ i=1,2,\dots,L $ に対して $ S_i $ と $ T_i $ が一致するか調べます。 2. $ S_i\ \neq\ T_i $ である $ i $ が存在する場合、そのような $ i $ のうち最小のものを $ j $ とします。そして、$ S_j $ と $ T_j $ を比較して、$ S_j $ が $ T_j $ よりアルファベット順で小さい場合は $ S\ \lt\ T $ 、そうでない場合は $ S\ \gt\ T $ と決定して、アルゴリズムを終了します。 3. $ S_i\ \neq\ T_i $ である $ i $ が存在しない場合、$ S $ と $ T $ の長さを比較して、$ S $ が $ T $ より短い場合は $ S\ \lt\ T $ 、長い場合は $ S\ \gt\ T $ と決定して、アルゴリズムを終了します。

N/A

N/A

### 制約 - $ 1\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ S,T $ は英小文字からなる長さ $ N $ の文字列 - $ N $ は整数 ### Sample Explanation 1 条件を満たす $ (i,j) $ の組は $ (0,0),(0,2),(2,0),(2,2) $ の $ 4 $ 個があります。 $ (i,j)=(1,2) $ は、$ f(S,i)= $`dba`$ ,f(T,j)= $`bca` であるため条件を満たしません。