GeT AC

题目描述

给你一个长度为 $N$ 的字符串 $S$，其由字符 $A$、$C$、$G$ 和 $T$ 组成。回答下面的 $Q$ 个查询：

查询 $i$（$1 \leq i \leq Q$）：给定整数 $l_i$ 和 $r_i$（1 \leq l_i < r_i \leq N）。考虑字符串 $S$ 从索引 $l_i$ 开始到索引 $r_i$ 结束（两端包含）的子串。在这个字符串中，子串 $AC$ 出现了多少次？

输入格式

输入从标准输入按如下格式给出： $N$ $Q$ $S$ $l_1$ $r_1$ : $l_Q$ $r_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

8 3
ACACTACG
3 7
2 3
1 8

2
0
3

提示

$2 \leq N \leq 10^5$ $1 \leq Q \leq 10^5$ $S$ 是长度为 $N$ 的字符串。 $S$ 中的每个字符都是 $A$、$C$、$G$ 或 $T$。 1 \leq l_i < r_i \leq N字符串 $T$ 的子串是通过从 $T$ 的开头和结尾去掉零个或多个字符得到的字符串。 例如，$ATCODER$ 的子串包括 $TCO$、$AT$、$CODER$、$ATCODER$ 和 $$（空字符串），但不包括 $AC$。查询 $1$：$S$ 中从索引 $3$ 到索引 $7$ 的子串是 $ACTAC$。在该字符串中，$AC$ 作为子串出现了两次。 查询 $2$：$S$ 中从索引 $2$ 到索引 $3$ 的子串是 $CA$。在该字符串中，$AC$ 作为子串出现了零次。 查询 $3$：$S$ 中从索引 $1$ 到索引 $8$ 的子串是 $ACACTACG$。在该字符串中，$AC$ 作为子串出现了三次。

标签: AtCoder|abc122C

来源

AtCoder|abc122C