← 返回题目列表

AtCoder · abc449_c

F. 舒适距离

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

分数: 300 点

问题陈述

给你一个字符串 S 长度 N 由小写英文字母组成。

查找整数对的数量 (i, j) 满足以下所有条件:

  • 1 \leq i \leq j \leq N
  • S_i = S_j
  • L \leq j - i \leq R

约束

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq L \leq R \leq N - 1
  • N, L, R 是整数。
  • S 是一个长度为 N 由小写英文字母组成。

输入

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

N L R
S

输出

输出答案。


示例输入 1

6 2 4
aabcba

示例输出 1

2

满足问题陈述中所有条件的整数对是 (i, j) = (2, 6), (3, 5),总共两对。


示例输入 2

9 3 6
aaaaaaaaa

示例输出 2

18

示例输入 3

10 2 6
aabbccaabb

示例输出 3

6