Score : $400$ points

问题描述

字符串 20230322 可以重新排列为 02320232，它是字符串 0232 的两次重复。

同样地，如果一个仅包含数字的字符串能够被重新排列（或已经）成为某个子字符串两次重复的形式，那么我们就称这个字符串是 快乐 的。

你将得到一个由数字组成的字符串 $S$。请找出满足以下所有条件的整数对 $(l, r)$ 的数量。

• $1 \le l \le r \le |S|$。 （其中 $|S|$ 表示字符串 $S$ 的长度。）
• 由 $S$ 中从第 $l$ 个字符到第 $r$ 个字符构成的连续子串是快乐的。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:16:08