← 返回题目列表

AtCoder · abc272_f

I. 两根弦

中文机器翻译题面 查看原题

分数: 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。

  1. 让 L 是最小的长度 S 和 T。 对于 i=1,2,\dots,L,我们检查是否 S_i 等于 T_i.
  2. 如果有 i 这样 S_i \neq T_i,让 j 是最小的这样 i。 比较 S_j 和 T_j,我们通过确定来终止算法 S \lt T if S_j 小于 T_j 按字母顺序排列,并且 S \gt T 否则。
  3. 如果没有 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