分数: 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