F - Two Strings
当前没有测试数据。
F - 两个字符串
得分：$500$ 分
问题描述
给定长度为 $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$ 的词典序大于 $T$，我们记作 $S \gt T$。
- 让 $L$ 成为 $S$ 和 $T$ 长度的最小值。对于 $i=1,2,\dots,L$，检查 $S_i$ 是否等于 $T_i$。
- 如果存在一个 $i$ 使得 $S_i \neq T_i$，让 $j$ 成为最小的这样的 $i$。比较 $S_j$ 和 $T_j$，如果在字母表中 $S_j$ 比 $T_j$ 小，我们通过确定 $S \lt T$ 来终止算法，否则我们确定 $S \gt T$。
- 如果不存在一个 $i$ 使得 $S_i \neq T_i$，比较 $S$ 和 $T$ 的长度，如果 $S$ 的长度小于 $T$，我们通过确定 $S \lt T$ 来终止算法，否则我们确定 $S \gt T$。
约束
- $1 \le N \le 2 \times 10^5$
- $S$ 和 $T$ 是长度为 $N$ 的字符串，由小写英文字母组成。
- $N$ 是整数。
输入
输入从标准输入中读取，格式如下：
输出
输出答案。
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