题目:
展开
题目描述
A, C, G, T からなる長さ NN の文字列 SS が与えられます。以下の QQ 個の問いに答えてください。
問 ii ( 1\ \leq\ i\ \leq\ Q1 ≤ i ≤ Q ): 整数 l_i,\ r_il
i
, r
i
( 1\ \leq\ l_i\ <\ r_i\ \leq\ N1 ≤ l
i
< r
i
≤ N ) が与えられる。 SS の先頭から l_il
i
文字目から r_ir
i
文字目までの (両端含む) 部分文字列を考える。この文字列に AC は部分文字列として何回現れるか。
You are given a string SS of length NN consisting of A, C, G and T. Answer the following QQ queries:
Query ii ( 1\ \leq\ i\ \leq\ Q1 ≤ i ≤ Q ): You will be given integers l_il
i
and r_ir
i
( 1\ \leq\ l_i\ <\ r_i\ \leq\ N1 ≤ l
i
< r
i
≤ N ). Consider the substring of SS starting at index l_il
i
and ending at index r_ir
i
(both inclusive). In this string, how many times does AC occurs as a substring?
输入格式
Input is given from Standard Input in the following format:
$ N $ $ Q $
$ S $
$ l_1 $ $ r_1 $
$ : $
$ l_Q $ $ r_Q $
输出格式
Print QQ lines. The ii -th line should contain the answer to the ii -th query.
题意翻译
您将得到一个长度为 NN 的字符串 SS,它由 A,C,G 和 T 组成。回答以下 QQ 个问题:
问题 i (1\leq i\leq Q)i(1≤i≤Q): 你将获得整数 l_il
i
and r_ir
i
(1\leq l_i < r_i \leq N)(1≤l
i
<r
i
≤N)。考虑 SS 的子字符串,从索引 l_il
i
开始到索引 r_ir
i
(包括两端)。 在此字符串中,AC 作为子字符串出现了多少次?
输入输出样例
输入 #1复制
8 3
ACACTACG
3 7
2 3
1 8
输出 #1复制
2
0
3
输入 #2复制
8 3
ACACTACG
3 7
2 3
1 8
输出 #2复制
2
0
3
说明/提示
注記
文字列 TT の部分文字列とは、 TT の先頭と末尾から 00 文字以上を取り去って得られる文字列です。
例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER, `` (空文字列) が含まれ、AC は含まれません。
制約
2\ \leq\ N\ \leq\ 10^52 ≤ N ≤ 10
5
1\ \leq\ Q\ \leq\ 10^51 ≤ Q ≤ 10
5
SS は長さ NN の文字列である。
SS の各文字は A, C, G, T のいずれかである。
1\ \leq\ l_i\ <\ r_i\ \leq\ N1 ≤ l
i
< r
i
≤ N
Notes
A substring of a string TT is a string obtained by removing zero or more characters from the beginning and the end of TT .
For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and `` (the empty string), but not AC.
Constraints
2\ \leq\ N\ \leq\ 10^52 ≤ N ≤ 10
5
1\ \leq\ Q\ \leq\ 10^51 ≤ Q ≤ 10
5
SS is a string of length NN .
Each character in SS is A, C, G or T.
1\ \leq\ l_i\ <\ r_i\ \leq\ N1 ≤ l
i
< r
i
≤ N
Sample Explanation 1
- 問 11 : SS の先頭から 33 文字目から 77 文字目までの部分文字列は ACTAC です。この文字列に AC は部分文字列として 22 回現れます。 - 問 22 : SS の先頭から 22 文字目から 33 文字目までの部分文字列は CA です。この文字列に AC は部分文字列として 00 回現れます。 - 問 33 : SS の先頭から 11 文字目から 88 文字目までの部分文字列は ACACTACG です。この文字列に AC は部分文字列として 33 回現れます。
Sample Explanation 2
- Query 11 : the substring of SS starting at index 33 and ending at index 77 is ACTAC. In this string, AC occurs twice as a substring. - Query 22 : the substring of SS starting at index 22 and ending at index 33 is CA. In this string, AC occurs zero times as a substring. - Query 33 : the substring of SS starting at index 11 and ending at index 88 is ACACTACG. In this string, AC occurs three times as a substring.
代码:
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int n, m;
string s;
cin >> n >> m >> s;
int a[m];
int x[m], y[m];
memset(a, 0, sizeof a);
for (int i = 0; i < m; i++) {
cin >> x[i] >> y[i];
}
for (int i = 0; i < m; i++) {
for (int j = x[i]; j <= y[i]; j++) {
while (s[j] == 'A' && s[j + 1] == 'C') {
a[i]++;
j++;
}
}
}
for (int i = 0; i < m; i++) {
cout << a[i] << endl;
}
return 0;
}