Score : $500$ points

问题描述

给定两个长度均为 $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 \lt T$ 和 $S \gt T$ 分别表示 $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_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$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given strings $S$ and $T$ of length $N$ each, consisting of lowercase English letters.

For a string $X$ and an integer $i$, let $f(X,i)$ be the string obtained by performing on $X$ the following operation $i$ times:

• Remove the first character of $X$ and append the same character to the end of $X$.

Find the number of integer pairs $(i,j)$ satisfying $0 \le i,j \le N-1$ such that $f(S,i)$ is lexicographically smaller than or equal to $f(T,j)$.

What is the lexicographical order?

Simply put, the lexicographical order is the order in which the words are arranged in a dictionary. Let us define it formally by describing an algorithm of finding the ordering of two distinct strings $S$ and $T$ consisting of lowercase English letters.

Here, we denote "the $i$-th character of a string $S$" by $S_i$. Also, we write $S \lt T$ and $S \gt T$ if $S$ is lexicographically smaller and larger than $T$, respectively.

1. Let $L$ be the smallest of the lengths of $S$ and $T$. For $i=1,2,\dots,L$, we check if $S_i$ equals $T_i$.
2. If there is an $i$ such that $S_i \neq T_i$, let $j$ be the smallest such $i$. Comparing $S_j$ and $T_j$, we terminate the algorithm by determining that $S \lt T$ if $S_j$ is smaller than $T_j$ in the alphabetical order, and that $S \gt T$ otherwise.
3. If there is no $i$ such that $S_i \neq T_i$, comparing the lengths of $S$ and $T$, we terminate the algorithm by determining that $S \lt T$ if $S$ is shorter than $T$, and that $S \gt T$ otherwise.

Constraints

• $1 \le N \le 2 \times 10^5$
• $S$ and $T$ are strings of length $N$ each, consisting of lowercase English letters.
• $N$ is an integer.

Input

The input is given from Standard Input in the following format:

$N$

$S$

$T$

Output

Print the answer.

Sample Input 1

3
adb
cab

Sample Output 1

4

There are $4$ pairs of $(i, j)$ satisfying the conditions: $(0,0),(0,2),(2,0)$, and $(2,2)$.

$(i,j)=(1,2)$ does not satisfy the conditions because $f(S,i)=$dba and $f(T,j)=$bca.

Sample Input 2

10
wsiuhwijsl
pwqoketvun

Sample Output 2

56

update @ 2024/3/10 11:28:29