两个字符串

题目描述

给你两个长度均为 $N$、由小写英文字母组成的字符串 $S$ 和 $T$。

对于字符串 $X$ 和整数 $i$,令 $f(X,i)$ 表示对 $X$ 执行以下操作 $i$ 次后得到的字符串:

删除 $X$ 的第一个字符,并将该字符追加到 $X$ 的末尾。

求满足 $0 \le i,j \le N-1$ 且 $f(S,i)$ 在字典序上小于或等于 $f(T,j)$ 的整数对 $(i,j)$ 的个数。

什么是字典序?

简单来说,字典序就是单词在字典中排列的顺序。下面通过描述一个比较两个由小写英文字母组成的不同字符串 $S$ 和 $T$ 的先后顺序的算法,给出形式化定义。

这里,我们用 $S_i$ 表示字符串 $S$ 的第 $i$ 个字符。另外,如果 $S$ 在字典序上小于、大于 $T$,我们分别记作 $S \lt T$、$S \gt T$。

设 $L$ 为 $S$ 和 $T$ 中较短的字符串的长度。对于 $i=1,2,\dots,L$,依次检查 $S_i$ 是否等于 $T_i$。

如果存在满足 $S_i \neq T_i$ 的 $i$,设 $j$ 为其中最小的一个。比较 $S_j$ 和 $T_j$,如果 $S_j$ 在字母序上小于 $T_j$,则判定 $S \lt T$,算法结束;否则判定 $S \gt T$。

如果不存在满足 $S_i \neq T_i$ 的 $i$,则比较 $S$ 和 $T$ 的长度,如果 $S$ 比 $T$ 短,则判定 $S \lt T$;否则判定 $S \gt T$。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$
$T$

输出格式

输出答案。

样例

3
adb
cab

4

满足条件的 $(i, j)$ 有 4 对:$(0,0),(0,2),(2,0)$ 和 $(2,2)$。

$(i,j)=(1,2)$ 不满足条件,因为 $f(S,i)=$dba 且 $f(T,j)=$bca。

10
wsiuhwijsl
pwqoketvun

56

数据范围

• $1 \le N \le 2 \times 10^5$
• $S$ 和 $T$ 是长度均为 $N$、由小写英文字母组成的字符串。
• $N$ 是整数。