G - Count Substring Query Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 575 点

問題文

英小文字からなる文字列 S が与えられます。

Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。

  • 英小文字からなる文字列 T_i が与えられる。S の部分文字列であって、T_i と一致するものは何通りあるか出力する。ただし、ある二つの部分文字列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとする。

制約

  • 1\leq |S|\leq 5\times 10^5
  • 1\leq Q\leq 5\times 10^5
  • 1\leq |T_i|\leq |S|
  • \displaystyle \sum_{i=1}^Q |T_i|\leq 5\times 10^5
  • S,T_i は英小文字列
  • Q は整数

入力

入力は以下の形式で標準入力から与えられる。

S
Q
T_1
T_2
\vdots
T_Q

出力

Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。

入力例 1

missisippi
5
i
s
a
is
missisippi

出力例 1

4
3
0
2
1

S の l 文字目から r 文字目までの部分文字列を S[l:r] とします。

  • 1 つ目のクエリについて、S の部分文字列であって i と一致するものは S[2:2],S[5:5],S[7:7],S[10:10] の 4 か所です。
  • 2 つ目のクエリについて、S の部分文字列であって s と一致するものは S[3:3],S[4:4],S[6:6] の 3 か所です。
  • 3 つ目のクエリについて、S の部分文字列であって a と一致するものは存在しません。
  • 4 つ目のクエリについて、S の部分文字列であって is と一致するものは S[2:3],S[5:6] の 2 か所です。
  • 5 つ目のクエリについて、S の部分文字列であって missisippi と一致するものは S[1:10] の 1 か所です。

入力例 2

aaaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

出力例 2

6
5
4
3
2
1

Score : 575 points

Problem Statement

You are given a string S consisting of lowercase English letters.

You are also given Q queries to process sequentially. The i-th query is described as follows:

  • A string T_i consisting of lowercase English letters is given. Print the number of substrings of S that equal T_i. Two substrings are distinguished if they are taken from different positions, even if they are equal as strings.

Constraints

  • 1 \leq |S| \leq 5 \times 10^5
  • 1 \leq Q \leq 5 \times 10^5
  • 1 \leq |T_i| \leq |S|
  • \displaystyle \sum_{i=1}^Q |T_i| \leq 5 \times 10^5
  • S and T_i are strings consisting of lowercase English letters.
  • Q is an integer.

Input

The input is given from Standard Input in the following format:

S
Q
T_1
T_2
\vdots
T_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

missisippi
5
i
s
a
is
missisippi

Sample Output 1

4
3
0
2
1

Let S[l:r] denote the substring of S from the l-th character through the r-th character.

  • For the 1st query, four substrings of S equal i: S[2:2], S[5:5], S[7:7], S[10:10].
  • For the 2nd query, three substrings of S equal s: S[3:3], S[4:4], S[6:6].
  • For the 3rd query, no substrings of S match a.
  • For the 4th query, two substrings of S equal is: S[2:3], S[5:6].
  • For the 5th query, one substring of S equals missisippi: S[1:10].

Sample Input 2

aaaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

Sample Output 2

6
5
4
3
2
1