分数: 500 点
问题陈述
给你字符串 S 和 T 长度 N 各由小写英文字母组成。
对于字符串 X 和一个整数 i,让 f(X,i) 是执行以下操作得到的字符串 X 以下操作 i 次:
- 删除第一个字符 X 并将相同的字符附加到末尾 X.
查找整数对的数量 (i,j) 满意 0 \le i,j \le N-1 这样 f(S,i) 按字典顺序小于或等于 f(T,j).
字典顺序是什么?
简单来说,词典顺序就是单词在词典中排列的顺序。 让我们通过描述查找两个不同字符串的排序的算法来正式定义它 S 和 T 由小写英文字母组成。
在这里,我们表示“ i- 字符串的第一个字符 S“通过 S_i。 另外,我们写 S \lt T 和 S \gt T if S 按字典顺序小于或大于 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 \lt T if S_j 小于 T_j 按字母顺序排列,并且 S \gt T 否则。
- 如果没有 i 这样 S_i \neq T_i,比较长度 S 和 T,我们通过确定来终止算法 S \lt T if S 短于 T,并且 S \gt T 否则。
约束
- 1 \le N \le 2 \times 10^5
- S 和 T 是长度的字符串 N 各由小写英文字母组成。
- N 是一个整数。
输入
输入由标准输入按以下格式给出:
N S T
输出
打印答案。
示例输入 1
3 adb cab
示例输出 1
4
有 4 对 (i, j) 满足条件: (0,0),(0,2),(2,0),和 (2,2).
(i,j)=(1,2) 不满足条件,因为 f(S,i)=dba 和 f(T,j)=bca.
示例输入 2
10 wsiuhwijsl pwqoketvun
示例输出 2
56