102725: [AtCoder]ABC272 F - Two Strings
Description
Score : $500$ points
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.
- 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$.
- 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.
- 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
Input
题意翻译
定义 $f(X,i)$ 表示把字符串 $X$ 的前 $i$ 个字母删除后整体拼接到 $X$ 的末尾形成的新字符串。比如令 $X=“saki”$ 则 $f(X,2)=“kisa”$。 空井咲有两个长为 $n$ 的字符串 $S$ 和 $T$，求满足 $f(S,i)$ 的字典序小于等于 $f(T,j)$ 的字典序 的 二元组 $(i,j)$ 对数。 要求 $0\le i,j\le n-1$。 数据满足 $n\le 2 \times 10^5$，$S$ 和 $T$ 均由小写字母组成。Output
问题描述
给你两个长度为 N 的字符串 S 和 T，由小写英文字符组成。
对于一个字符串 X 和一个整数 i，令 f(X,i) 为通过对 X 进行以下操作 i 次后得到的字符串：
- 移除 X 的第一个字符，并将该字符添加到 X 的末尾。
找出满足 0 ≤ i,j ≤ N-1 的整数对 (i,j)，使得 f(S,i) 在字典序上小于等于 f(T,j)。
什么是字典序？
简单来说，字典序就是字典中单词的排列顺序。让我们通过描述一种方法来正式定义它，以找出由小写英文字符组成的两个不同字符串 S 和 T 的顺序。
在这里，我们用 "字符串 S 的第 i 个字符" 表示为 S_i。此外，我们用 S \lt T 和 S \gt T 表示 S 在字典序上小于和大于 T，分别。
- 让 L 为 S 和 T 的长度的较小值。对于 i=1,2,\dots,L，我们检查 S_i 是否等于 T_i。
- 如果存在一个 i 使得 S_i \neq T_i，那么让 j 为使得 S_i \neq T_i 的 i 的最小值。比较 S_j 和 T_j，我们通过确定 S_j 是否在字母顺序上小于 T_j 来终止算法，从而确定 S \lt T；否则，我们确定 S \gt T。
- 如果不存在 i 使得 S_i \neq T_i，那么我们通过比较 S 和 T 的长度来终止算法，从而确定 S \lt T，如果 S 更短；否则，我们确定 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