267 . 小風數堅果

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

ioicamp ioicamp-2020

Description

又到了堅果盛產的季節，現在小風家的倉庫堆滿了各式各樣的堅果，這次小風決定來整理堅果。

分類堅果是一件很累的事情，有些堅果長得像棋盤，有些堅果長得像稿紙，有些堅果長的很好吃。

今天小風正在測量兩個堅果 $S$、$T$ 的相似度，一個堅果的特徵值可以用一個字串來表示，為了精確的測量出堅果的相似度，小風準備了 $q$ 個問題來檢測兩個堅果的關聯性。對於每個詢問 $a_i, b_i$，小風想要知道 $T_{a_i}...T_{b_i}$ 這個子字串在 $S$ 中出現幾次。

但是因為堅果真的很好吃，因此請你來回答這個問題。

Input Format

第一、二行分別有一個字串 $S$、$T$。

接下來有一行 $q$，代表詢問的數量。

再接下來有 $q$ 行，第 $i$ 行上有兩個正整數 $a_i, b_i$。

  • $1\le |S|, |T| \le 3\times 10^ 6$
  • $1\le q \le 3\times 10^ 6$
  • $1\le a_i \le b_i \le |T|$
  • $a_i \le a_{i+1}, b_i \le b_{i+1}$

Output Format

對於每個詢問，請輸出一個整數代表出現的次數。

Sample Input 1

ababa
caaba
5
1 1
1 2
2 2
2 3
3 5

Sample Output 1

0
0
3
0
2

Sample Input 2

cabbcbcbcc
aabc
6
1 1
1 2
2 2
2 3
3 3
3 4

Sample Output 2

1
0
1
1
4
3

Hints

Problem Source

IOICamp 2020 Day5 pD

Subtasks

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

Testdata and Limits

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