F - Two Strings Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ 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 が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

  1. S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
  2. S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、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 と決定して、アルゴリズムを終了します。

制約

  • 1 \le N \le 2 \times 10^5
  • S,T は英小文字からなる長さ N の文字列
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N
S
T

出力

答えを出力せよ。

入力例 1

3
adb
cab

出力例 1

4

条件を満たす (i,j) の組は (0,0),(0,2),(2,0),(2,2) の 4 個があります。

(i,j)=(1,2) は、f(S,i)=dba,f(T,j)=bca であるため条件を満たしません。

入力例 2

10
wsiuhwijsl
pwqoketvun

出力例 2

56

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.

  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