题目描述

長さ $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$ $S$ $T$

输出格式

答えを出力せよ。

题目大意

定义 $f(X,i)$ 表示把字符串 $X$ 的前 $i$ 个字母删除后整体拼接到 $X$ 的末尾形成的新字符串。比如令 $X=“saki”$ 则 $f(X,2)=“kisa”$。

空井咲有两个长为 $n$ 的字符串 $S$ 和 $T$，求满足 $f(S,i)$ 的字典序小于等于 $f(T,j)$ 的字典序 的 二元组 $(i,j)$ 对数。

要求 $0\le i,j\le n-1$。

数据满足 $n\le 2 \times 10^5$，$S$ 和 $T$ 均由小写字母组成。

3
adb
cab

4

10
wsiuhwijsl
pwqoketvun

56

提示

制約

• $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 であるため条件を満たしません。