

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
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
は部分文字列として何回現れるか。
注記
文字列 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
入力
入力は以下の形式で標準入力から与えられる。
N Q S l_1 r_1 : l_Q r_Q
出力
Q 行出力せよ。i 行目に問 i への答えを出力すること。
入力例 1
8 3 ACACTACG 3 7 2 3 1 8
出力例 1
2 0 3
- 問 1: S の先頭から 3 文字目から 7 文字目までの部分文字列は
ACTAC
です。この文字列にAC
は部分文字列として 2 回現れます。 - 問 2: S の先頭から 2 文字目から 3 文字目までの部分文字列は
CA
です。この文字列にAC
は部分文字列として 0 回現れます。 - 問 3: S の先頭から 1 文字目から 8 文字目までの部分文字列は
ACACTACG
です。この文字列にAC
は部分文字列として 3 回現れます。
Score : 300 points
Problem Statement
You are given a string S of length N consisting of A
, C
, G
and T
. Answer the following Q queries:
- Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does
AC
occurs as a substring?
Notes
A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.
For example, the substrings of ATCODER
include TCO
, AT
, CODER
, ATCODER
and (the empty string), but not
AC
.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- S is a string of length N.
- Each character in S is
A
,C
,G
orT
. - 1 \leq l_i < r_i \leq N
Input
Input is given from Standard Input in the following format:
N Q S l_1 r_1 : l_Q r_Q
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
8 3 ACACTACG 3 7 2 3 1 8
Sample Output 1
2 0 3
- Query 1: the substring of S starting at index 3 and ending at index 7 is
ACTAC
. In this string,AC
occurs twice as a substring. - Query 2: the substring of S starting at index 2 and ending at index 3 is
CA
. In this string,AC
occurs zero times as a substring. - Query 3: the substring of S starting at index 1 and ending at index 8 is
ACACTACG
. In this string,AC
occurs three times as a substring.