E - Pattern Search in DNA Sequences Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は生物情報学の研究室で、遺伝子の発現レベルの解析を行っています。この研究では、各サンプルの各位置における発現レベルを H（高）、M（中）、L（低）の3種類の文字で表し、それらを並べた文字列として記録しています。

研究室には N 個のサンプルがあり、それぞれの発現レベル列が文字列 S_1, S_2, \ldots, S_N として記録されています。また、高橋君は特定の機能に関連すると考えられる基準パターン P を持っています。

青木君は高橋君の研究を手伝うことになり、基準パターンの一部を反転させた変形パターンが各サンプル中に何回出現するかを調べる解析プログラムを作ることにしました。

具体的には、Q 個のクエリが与えられます。j 番目（1 \leq j \leq Q）のクエリでは、サンプル番号 i_j、区間の左端 l_j、区間の右端 r_j の整数の組 (i_j, l_j, r_j) が与えられ、以下の手順で答えを求めます。

変形パターンの生成： 基準パターン P の l_j 文字目から r_j 文字目まで（1-indexed、両端含む）を反転し、それ以外の部分はそのまま保持することで、変形パターン P'_j を生成します。P'_j の長さは P の長さ |P| と等しくなります。

例えば、P = HMLLM のとき l_j = 2, r_j = 4 ならば、2文字目から4文字目の MLL を反転して LLM とし、P'_j = HLLMM となります。

出現回数の計算： サンプル S_{i_j} の中で、P'_j と一致する長さ |P| の連続部分文字列の個数を数えます。より正確には、S_{i_j} の a 文字目から a + |P| - 1 文字目までの部分文字列が P'_j と一致するような開始位置 a（1 \leq a \leq |S_{i_j}| - |P| + 1）の個数を求めます。|S_{i_j}| < |P| の場合、条件を満たす開始位置は存在しないため、出現回数は 0 です。開始位置が異なれば、出現箇所が重なっていてもそれぞれ別々に数えます。

なお、変形操作はクエリごとに独立であり、毎回元の基準パターン P に対して操作を行います。

各クエリについて、上記の出現回数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq |P| \leq 5 \times 10^5
  • 1 \leq |S_i| \leq 5 \times 10^5（1 \leq i \leq N）
  • \sum_{i=1}^{N} |S_i| \leq 5 \times 10^5
  • P および各 S_i は H, M, L のみからなる
  • 1 \leq i_j \leq N（1 \leq j \leq Q）
  • 1 \leq l_j \leq r_j \leq |P|（1 \leq j \leq Q）
  • 入力はすべて整数または文字列で与えられる

入力

N Q
P
S_1
S_2
\vdots
S_N
i_1 l_1 r_1
i_2 l_2 r_2
\vdots
i_Q l_Q r_Q
  • 1 行目には、サンプル数を表す整数 N とクエリ数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、基準パターンを表す文字列 P が与えられる。P は H, M, L のみからなる。
  • 続く N 行には、各サンプルの発現レベル列を表す文字列 S_i（1 \leq i \leq N）が 1 行に 1 つずつ与えられる。各 S_i は H, M, L のみからなる。
  • 続く Q 行には、各クエリの情報が 1 行に 1 つずつ与えられる。j 番目のクエリでは、検索対象のサンプル番号 i_j、反転する区間の左端 l_j、右端 r_j が、それぞれ整数としてスペース区切りで与えられる（1 \leq j \leq Q）。

出力

Q 行出力せよ。j 行目（1 \leq j \leq Q）には、j 番目のクエリに対する答え、すなわち変形パターン P'_j がサンプル S_{i_j} 中に連続部分文字列として出現する回数を整数で出力せよ。

入力例 1

2 4
HMLLM
HLLMMHMLLMHMLLM
LLMHMHLLMM
1 2 4
1 1 5
2 1 3
2 5 5

出力例 1

1
1
0
0

入力例 2

3 5
HML
HMLHML
LMHLMH
HHHH
1 1 1
1 1 3
2 1 3
3 2 2
2 2 3

出力例 2

2
0
2
0
1

入力例 3

5 12
HMLLHMMHLH
HMLLHMMHLHHMLLHMMHLH
HLMMLHMHLHMLLHMMHLLH
LLLLHHHHMMMMHMLLHMMHLH
MLHMLHMLHMLHMLHMLHMLH
HHMLLHMMHLHLLHMMHLLMHH
1 1 10
1 3 7
2 2 9
2 5 5
3 1 4
3 7 10
4 1 3
4 4 8
5 2 6
5 1 10
1 6 10
2 1 1

出力例 3

0
0
0
0
0
0
0
0
0
0
0
0

入力例 4

8 20
HMLLMHHLMLMHHLLMMHLMHLML
HMLLMHHLMLMHHLLMMHLMHLMLHMLLMHHLMLMHHLLMMHLMHLML
LLHHMMLMLHHMLLMHMLHMLMLLHMMHHLLMMHLMHLMLHMLLMHH
MMMMHHHHLLLLHMLLMHHLMLMHHLLMMHLMHLMLLLLLHHHHMMMM
HMLHMLHMLHMLHMLHMLHMLHMLHMLHMLHMLHML
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
MLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLML
HMLLMHHLMLMHHLLMMHLMHLMLLMLHMHMLMMHLLHHMMLMLHH
1 1 24
1 6 18
1 12 12
2 1 5
2 10 24
3 4 20
3 15 24
4 1 3
4 2 23
5 1 24
5 7 7
6 1 1
6 20 24
7 3 22
7 8 16
8 1 24
8 5 14
8 11 21
2 6 6
3 1 24

出力例 4

0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

入力例 5

1 1
H
M
1 1 1

出力例 5

0

Score : 433 pts

Problem Statement

Takahashi is working in a bioinformatics laboratory, analyzing gene expression levels. In this research, the expression level at each position of each sample is represented by one of three characters: H (high), M (medium), or L (low), and recorded as a string of these characters.

The laboratory has N samples, and their expression level sequences are recorded as strings S_1, S_2, \ldots, S_N. Takahashi also has a reference pattern P that is believed to be related to a specific function.

Aoki has decided to help Takahashi's research by creating an analysis program that counts how many times a modified pattern—obtained by reversing a part of the reference pattern—appears in each sample.

Specifically, Q queries are given. For the j-th query (1 \leq j \leq Q), a tuple of integers (i_j, l_j, r_j) is given, representing a sample number i_j, the left endpoint l_j, and the right endpoint r_j of an interval. The answer is determined by the following procedure.

Generation of the modified pattern: Reverse the substring of the reference pattern P from the l_j-th character to the r_j-th character (1-indexed, both endpoints inclusive), while keeping the remaining parts unchanged, to generate the modified pattern P'_j. The length of P'_j equals the length |P| of P.

For example, if P = HMLLM and l_j = 2, r_j = 4, then the substring from the 2nd to 4th characters MLL is reversed to LLM, resulting in P'_j = HLLMM.

Counting occurrences: Count the number of contiguous substrings of length |P| in sample S_{i_j} that match P'_j. More precisely, find the number of starting positions a (1 \leq a \leq |S_{i_j}| - |P| + 1) such that the substring of S_{i_j} from the a-th character to the (a + |P| - 1)-th character matches P'_j. If |S_{i_j}| < |P|, no valid starting position exists, so the occurrence count is 0. Even if occurrences overlap, they are counted separately as long as their starting positions differ.

Note that the modification operation is independent for each query; each time, the operation is applied to the original reference pattern P.

For each query, determine the above occurrence count.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq |P| \leq 5 \times 10^5
  • 1 \leq |S_i| \leq 5 \times 10^5 (1 \leq i \leq N)
  • \sum_{i=1}^{N} |S_i| \leq 5 \times 10^5
  • P and each S_i consist only of H, M, L
  • 1 \leq i_j \leq N (1 \leq j \leq Q)
  • 1 \leq l_j \leq r_j \leq |P| (1 \leq j \leq Q)
  • All inputs are given as integers or strings

Input

N Q
P
S_1
S_2
\vdots
S_N
i_1 l_1 r_1
i_2 l_2 r_2
\vdots
i_Q l_Q r_Q
  • The first line contains two space-separated integers N (the number of samples) and Q (the number of queries).
  • The second line contains the string P representing the reference pattern. P consists only of H, M, L.
  • The following N lines each contain a string S_i (1 \leq i \leq N) representing the expression level sequence of each sample. Each S_i consists only of H, M, L.
  • The following Q lines each contain the information for one query. For the j-th query, the sample number i_j, the left endpoint l_j, and the right endpoint r_j of the interval to reverse are given as space-separated integers (1 \leq j \leq Q).

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain a single integer: the answer to the j-th query, i.e., the number of times the modified pattern P'_j appears as a contiguous substring in sample S_{i_j}.

Sample Input 1

2 4
HMLLM
HLLMMHMLLMHMLLM
LLMHMHLLMM
1 2 4
1 1 5
2 1 3
2 5 5

Sample Output 1

1
1
0
0

Sample Input 2

3 5
HML
HMLHML
LMHLMH
HHHH
1 1 1
1 1 3
2 1 3
3 2 2
2 2 3

Sample Output 2

2
0
2
0
1

Sample Input 3

5 12
HMLLHMMHLH
HMLLHMMHLHHMLLHMMHLH
HLMMLHMHLHMLLHMMHLLH
LLLLHHHHMMMMHMLLHMMHLH
MLHMLHMLHMLHMLHMLHMLH
HHMLLHMMHLHLLHMMHLLMHH
1 1 10
1 3 7
2 2 9
2 5 5
3 1 4
3 7 10
4 1 3
4 4 8
5 2 6
5 1 10
1 6 10
2 1 1

Sample Output 3

0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 4

8 20
HMLLMHHLMLMHHLLMMHLMHLML
HMLLMHHLMLMHHLLMMHLMHLMLHMLLMHHLMLMHHLLMMHLMHLML
LLHHMMLMLHHMLLMHMLHMLMLLHMMHHLLMMHLMHLMLHMLLMHH
MMMMHHHHLLLLHMLLMHHLMLMHHLLMMHLMHLMLLLLLHHHHMMMM
HMLHMLHMLHMLHMLHMLHMLHMLHMLHMLHMLHML
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
MLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLML
HMLLMHHLMLMHHLLMMHLMHLMLLMLHMHMLMMHLLHHMMLMLHH
1 1 24
1 6 18
1 12 12
2 1 5
2 10 24
3 4 20
3 15 24
4 1 3
4 2 23
5 1 24
5 7 7
6 1 1
6 20 24
7 3 22
7 8 16
8 1 24
8 5 14
8 11 21
2 6 6
3 1 24

Sample Output 4

0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 5

1 1
H
M
1 1 1

Sample Output 5

0