D - ほぼ同じ信号パターン 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、ある通信システムのログを解析しています。このシステムでは、 0 と 1 のみからなる長さ N のビット列 S が記録されています。

高橋君は、この信号ログの中から「ほぼ同じ」区間のペアを見つけたいと考えています。

S の連続部分文字列を、開始位置 l と終了位置 r の組 (l, r) （ 1 \leq l \leq r \leq N ）で表します。これは S の l 文字目から r 文字目までの連続した部分を指し、その長さは r - l + 1 です。

2つの連続部分文字列の組 ((l_1, r_1), (l_2, r_2)) が「ほぼ同じ」ペアであるとは、以下の条件をすべて満たすことを言います。

  • (l_1, r_1) \neq (l_2, r_2) である。すなわち、 l_1 \neq l_2 または r_1 \neq r_2 である。
  • r_1 - l_1 = r_2 - l_2 である。すなわち、2つの連続部分文字列の長さが等しい。
  • 2つの連続部分文字列の長さを L とする。先頭から i 番目の文字同士（ 1 \leq i \leq L ）を比較したとき、文字が異なる位置 i がちょうど 1 つである（すなわち、ハミング距離がちょうど 1 である）。

ペアは 順序なし で数えます。すなわち、 ((l_1, r_1), (l_2, r_2)) と ((l_2, r_2), (l_1, r_1)) は同一のペアとみなします。

なお、部分文字列は位置の組 (l, r) で区別します。 (l_1, r_1) \neq (l_2, r_2) であれば、たとえ取り出した文字列の内容が一致していても、それらは異なる部分文字列として扱います。

条件を満たすペアの個数を求めてください。

制約

  • 1 \leq N \leq 5000
  • N は整数である。
  • S は 0 と 1 のみからなる長さ N の文字列である。

入力

N
S
  • 1 行目には、ビット列の長さを表す整数 N が与えられる。
  • 2 行目には、 0 と 1 のみからなる長さ N の文字列 S が与えられる。

出力

条件を満たす順序なしペアの個数を整数として 1 行で出力せよ。

入力例 1

3
101

出力例 1

2

入力例 2

4
0011

出力例 2

7

入力例 3

20
01101001011010010110

出力例 3

298

入力例 4

50
01001101011010001001110101100110100101101001101011

出力例 4

2136

入力例 5

1
0

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi is analyzing the log of a communication system. In this system, a bit string S of length N consisting only of 0 and 1 is recorded.

Takahashi wants to find pairs of "nearly identical" intervals in this signal log.

A contiguous substring of S is represented by a pair of starting position l and ending position r, denoted (l, r) (1 \leq l \leq r \leq N). This refers to the contiguous portion from the l-th character to the r-th character of S, and its length is r - l + 1.

A pair of two contiguous substrings ((l_1, r_1), (l_2, r_2)) is called a "nearly identical" pair if and only if all of the following conditions are satisfied:

  • (l_1, r_1) \neq (l_2, r_2). That is, l_1 \neq l_2 or r_1 \neq r_2.
  • r_1 - l_1 = r_2 - l_2. That is, the two contiguous substrings have equal length.
  • Let L be the length of the two contiguous substrings. When comparing the i-th characters from the beginning (1 \leq i \leq L), there is exactly 1 position i where the characters differ (that is, the Hamming distance is exactly 1).

Pairs are counted as unordered. That is, ((l_1, r_1), (l_2, r_2)) and ((l_2, r_2), (l_1, r_1)) are considered the same pair.

Note that substrings are distinguished by their position pair (l, r). Even if the actual string contents are identical, if (l_1, r_1) \neq (l_2, r_2), they are treated as different substrings.

Find the number of pairs that satisfy the conditions.

Constraints

  • 1 \leq N \leq 5000
  • N is an integer.
  • S is a string of length N consisting only of 0 and 1.

Input

N
S
  • The first line contains an integer N representing the length of the bit string.
  • The second line contains a string S of length N consisting only of 0 and 1.

Output

Output the number of unordered pairs satisfying the conditions as a single integer on one line.

Sample Input 1

3
101

Sample Output 1

2

Sample Input 2

4
0011

Sample Output 2

7

Sample Input 3

20
01101001011010010110

Sample Output 3

298

Sample Input 4

50
01001101011010001001110101100110100101101001101011

Sample Output 4

2136

Sample Input 5

1
0

Sample Output 5

0