/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
20230322 は並べ替えると 02320232 となり、これは 0232 を 2 度繰り返しています。
このように、数字のみからなる文字列であって、適切に文字を並び替える (そのままでもよい) ことによって同じ列を 2 度繰り返すようにできるものを 嬉しい列 と呼びます。
数字のみからなる文字列 S が与えられるので、以下の条件を全て満たす整数の組 (l,r) はいくつあるか求めてください。
- 1 \le l \le r \le |S| ( |S| は S の長さ)
- S の l 文字目から r 文字目までの (連続する) 部分文字列は嬉しい列である。
制約
- S は数字のみからなる長さ 1 以上 5 \times 10^5 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを整数として出力せよ。
入力例 1
20230322
出力例 1
4
S= 20230322 です。
条件を満たす整数組 (l,r) は (1,6),(1,8),(2,7),(7,8) の 4 つです。
入力例 2
0112223333444445555556666666777777778888888889999999999
出力例 2
185
S の先頭が 0 である場合もあります。
入力例 3
3141592653589793238462643383279502884197169399375105820974944
出力例 3
9
Score : 400 points
Problem Statement
The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string S consisting of digits. Find the number of pairs of integers (l,r) satisfying all of the following conditions.
- 1 \le l \le r \le |S|. (|S| is the length of S.)
- The (contiguous) substring formed of the l-th through r-th characters of S is happy.
Constraints
- S is a string consisting of digits whose length is between 1 and 5 \times 10^5, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print an integer representing the answer.
Sample Input 1
20230322
Sample Output 1
4
We have S= 20230322.
Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).
Sample Input 2
0112223333444445555556666666777777778888888889999999999
Sample Output 2
185
S may begin with 0.
Sample Input 3
3141592653589793238462643383279502884197169399375105820974944
Sample Output 3
9