AT_abc272_f [ABC272F] Two Strings

题目描述

给定两个长度为 $N$ 的仅包含小写英文字母的字符串 $S$ 和 $T$。

对于字符串 $X$ 和整数 $i$，定义 $f(X,i)$ 为对 $X$ 执行以下操作 $i$ 次后得到的字符串：

• 删除 $X$ 的首字母，并将该字母插入到 $X$ 的末尾。

请你计算满足 $0 \leq i, j \leq N-1$ 的非负整数对 $(i, j)$ 中，有多少对满足 $f(S, i)$ 的字典序小于等于 $f(T, j)$。

什么是字典序？字典序简单来说就是“单词在字典中出现的顺序”。更严格地说，判断由小写英文字母组成的不同字符串 $S$、$T$ 的大小关系的算法如下：

记 $S$ 的第 $i$ 个字符为 $S_i$。若 $S$ 的字典序小于 $T$，记为 $S < T$，大于则记为 $S > T$。

1. 设 $L$ 为 $S$ 和 $T$ 中较短的字符串的长度。对于 $i=1,2,\dots,L$，比较 $S_i$ 和 $T_i$ 是否相同。
2. 如果存在 $S_i \neq T_i$，取最小的此类 $i$，记为 $j$。若 $S_j$ 在字母表中小于 $T_j$，则 $S < T$，否则 $S > T$，算法结束。
3. 如果所有 $S_i = T_i$，则比较 $S$ 和 $T$ 的长度，短的字典序更小，算法结束。

输入格式

输入从标准输入读取，格式如下：

$N$ $S$ $T$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3
adb
cab

输出 #1

4

输入输出样例 #2

输入 #2

10
wsiuhwijsl
pwqoketvun

输出 #2

56

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $S,T$ 均为长度为 $N$ 的小写英文字母字符串
• $N$ 为整数

样例解释 1

满足条件的 $(i, j)$ 共有 $4$ 组，分别为 $(0,0),(0,2),(2,0),(2,2)$。例如，$(i,j)=(1,2)$ 时，$f(S,1)=\texttt{dba}$，$f(T,2)=\texttt{bca}$，不满足条件。

由 ChatGPT 4.1 翻译