← 返回题目列表

AtCoder · abc430_c

F. 卡车司机

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

分数: 300 点

问题陈述

在AtCoder Country,有一条规定“卡车司机必须至少休息 B 驾驶分钟 A 分钟或更长时间。”

给你一个字符串 S 长度 N 组成 a 和 b和正整数 A 和 B。求整数对的数量 (l,r) 满足以下所有条件。

  • 1\leq l \leq r \leq N
  • 数量 a 中的子字符串 l- 第一个字符 r- 第一个字符 S 大于或等于 A.
  • 数量 b 中的子字符串 l- 第一个字符 r- 第一个字符 S 小于 B.

约束

  • 1\leq N \leq 3\times 10^5
  • 1 \leq A,B \leq N
  • S 是一个长度为 N 组成 a 和 b.
  • 所有输入数字均为整数。

输入

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

N A B
S

输出

打印答案。


示例输入 1

11 4 2
abbaaabaaba

示例输出 1

3

对 (l,r) 满足条件的是 (4,8),(4,9),(5,9),这是三对。


示例输入 2

13 1 2
bbbbbbbbbbbbb

示例输出 2

0

没有对 (l,r) 满足条件。