#P5641. 前缀和

    ID: 4642 传统题 1000ms 256MiB 尝试: 91 已通过: 21 难度: 4 上传者: 标签>CF1600普及+/提高-KMPborder 链计数 DP前缀出现次数统计

前缀和

题目描述

给你一个字符串 ss,要求计算所有长度为偶数的前缀在整个字符串中出现的总次数。

输入格式

输入仅一行,包含一个字符串 ss。

字符串的长度满足 ∣s∣≤200000|s| \leq 200000。

输出格式

输出仅一行,一个整数,表示所有长度为偶数的前缀在整个字符串中出现的总次数。

abababc
6

样例解释

对于样例输入 abababc:

  • 长度为 22 的前缀是 ab,它在字符串中出现了 33 次(起始位置分别为 1,3,51, 3, 5)。
  • 长度为 44 的前缀是 abab,它在字符串中出现了 22 次(起始位置分别为 1,31, 3)。
  • 长度为 66 的前缀是 ababab,它在字符串中出现了 11 次(起始位置为 11)。

因此,总次数为 3+2+1=63 + 2 + 1 = 6。

相关

在下列比赛中:

kmp