AT_abc122_c [ABC122C] GeT AC

题目描述

给定一个由 A、C、G、T 组成的长度为 $N$ 的字符串 $S$。请回答以下 $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$
$\vdots$
$l_Q$ $r_Q$

输出格式

输出共 $Q$ 行。第 $i$ 行输出问题 $i$ 的答案。

样例 1

输入

8 3
ACACTACG
3 7
2 3
1 8

输出

2
0
3

说明/提示

注释

字符串 $T$ 的子串是指从 $T$ 的开头和结尾各去掉 $0$ 个或多个字符后得到的字符串。

例如，ATCODER 的子串包括 TCO、AT、CODER、ATCODER、``（空字符串），但不包括 AC。

约束

• $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$

样例解释 1

• 问题 $1$：$S$ 的第 $3$ 个字符到第 $7$ 个字符的子串为 ACTAC。在这个字符串中，AC 作为子串出现了 $2$ 次。
• 问题 $2$：$S$ 的第 $2$ 个字符到第 $3$ 个字符的子串为 CA。在这个字符串中，AC 作为子串出现了 $0$ 次。
• 问题 $3$：$S$ 的第 $1$ 个字符到第 $8$ 个字符的子串为 ACACTACG。在这个字符串中，AC 作为子串出现了 $3$ 次。

由 ChatGPT 4.1 翻译