Three Days Ago

题目描述

字符串 $20230322$ 可以重排为 $02320232$，它是字符串 $0232$ 重复两次的结果。
类似地，当一个由数字组成的字符串可以被重排成（或本来就是）某个字符串重复两次时，该字符串被称为 happy。
给定一个由数字组成的字符串 $S$。求满足下列所有条件的整数对 $(l,r)$ 的个数。

$1 \le l \le r \le |S|$。($|S|$ 为 $S$ 的长度。) 由 $S$ 的第 $l$ 到第 $r$ 个字符组成的（连续）子串是 happy。

输入格式

输入按照标准输入给出，格式如下： $S$

输出格式

输出一个整数，表示答案。

20230322

4

0112223333444445555556666666777777778888888889999999999

185

3141592653589793238462643383279502884197169399375105820974944

9

提示

$S$ 是一个由数字组成的字符串，长度在 $1$ 到 $5 \times 10^5$ 之间（含两端）。我们有 $S=$ $20230322$。
满足条件的四个整数对 $(l,r)$ 如下：$(1,6)$，$(1,8)$，$(2,7)$，和 $(7,8)$。
$S$ 可能以 $0$ 开头。

标签: AtCoder|abc295D

来源

AtCoder|abc295D