TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

50.0% (1/2)

Tags

Description

總召好帥!!!
給你兩個長度皆為 $N$ 的字串 $S,T$ ,以及很多個詢問字串 $P$ ,對於每個詢問字串求有多少個配對 $(i,j)$ 滿足 $S$ 的前 $i$ 個字元和 $T$ 的第 $i+1$ 個字元以後的這兩個子字串皆不包含 $P$ ,而若把這兩個字串串接起來後會在位置 $j$ 出現 $P$ 。
正式的來說就是 $S_{1..i}, T_{i+1..N}$ 皆不包含 $P$ ,而 $S_{1..i}+T_{i+1..N}$ (字串串接)包含 $P$ 在位置 $j$ ,也就是 $(S_{1..i}+T_{i+1..N})_{j..j+|P|-1}=P$,求有多少相異的 $(i,j)$ 滿足條件。

Input Format

前兩行各有一個字串 $S,T$ 為給定的兩字串。

第三行有一個正整數 $Q$ 代表詢問筆數。

接下來有 $Q$ 行每行一個詢問的字串 $P$。

  • $1\le |S|=|T|\le 5\times 10^ {4}$
  • $1\le Q\le 5\times 10^ {4}$
  • $1\le \sum|P|\le 5\times 10^ {4}$
  • 所有字串皆只包含小寫英文字母

Output Format

輸出一共 $Q$ 行,對於每筆詢問輸出一個正整數為題目所求的答案。

Sample Input 1

abababa
abaabba
2
aba
bb

Sample Output 1

2
0

Sample Input 2

abcccba
bacccab
2
abccc
ccc

Sample Output 2

3
2

Hints

Problem Source

IOICamp 2021 Day3 pD

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~29 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 1 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2
15 2000 262144 65536 2
16 2000 262144 65536 2
17 2000 262144 65536 2
18 2000 262144 65536 2
19 2000 262144 65536 2
20 2000 262144 65536 2
21 2000 262144 65536 2
22 2000 262144 65536 2
23 2000 262144 65536 2
24 2000 262144 65536 2
25 2000 262144 65536 2
26 2000 262144 65536 2
27 2000 262144 65536 2
28 2000 262144 65536 2
29 2000 262144 65536 2