← 返回题目列表

AtCoder · abc433_c

F. 1122 子串 2

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个字符串 S 由数字组成。

一个字符串 T 被称为 1122 字符串 如果满足以下所有条件。 (定义与问题F相同。)

  • T 是由数字组成的非空字符串。
  • |T| 是偶数,其中 |T| 表示字符串的长度 T.
  • 所有字符来自 1-st 通过 \frac{|T|}2- 第一个字符 T 是相同的数字。
  • 所有字符来自 (\frac{|T|}2+1)-th 通过 |T|- 第一个字符 T 是相同的数字。
  • 添加 1 到数字 1-st 字符 T 给出的数字 |T|- 第一个字符。

例如, 1122, 01,和 444555 是 1122 个字符串,但是 1222 和 90 不是 1122 个字符串。

查找数量 子字符串 of S 是 1122 个字符串。

如果从不同位置提取两个子字符串,即使它们与字符串相同,也会单独计数。

约束

  • S 是由长度介于 1 和 10^6,包括在内。

输入

输入由标准输入按以下格式给出:

S

输出

输出非空子串的个数 S 是 1122 个字符串。


示例输入 1

1122

示例输出 1

2

以下两个子字符串满足条件。

  • 12 摘自 2-nd 通过 3-rd 字符 S
  • 1122 摘自 1-st 通过 4- 第一个字符 S

因此,输出 2.


示例输入 2

7788788

示例输出 2

3

请注意,如果从不同位置提取两个子字符串,即使它们与字符串相同,也会单独计数。


示例输入 3

2025

示例输出 3

0

可能不存在 1122 字符串的子字符串。


示例输入 4

1112222334445556555

示例输出 4

11