1016B.md (1824B)
1 Source: https://codeforces.com/problemset/problem/1016/B 2 3 B. Segment Occurrences 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two strings $s$ and $t$, both consisting only of lowercase Latin letters. 22 23 The substring $s[l..r]$ is the string which is obtained by taking characters $s_l, s_{l + 1}, \dots, s_r$ without changing the order. 24 25 Each of the occurrences of string $a$ in a string $b$ is a position $i$ ($1 \le i \le |b| - |a| + 1$) such that $b[i..i + |a| - 1] = a$ ($|a|$ is the length of string $a$). 26 27 You are asked $q$ queries: for the $i$-th query you are required to calculate the number of occurrences of string $t$ in a substring $s[l_i..r_i]$. 28 29 Input 30 31 The first line contains three integer numbers $n$, $m$ and $q$ ($1 \le n, m \le 10^3$, $1 \le q \le 10^5$) — the length of string $s$, the length of string $t$ and the number of queries, respectively. 32 33 The second line is a string $s$ ($|s| = n$), consisting only of lowercase Latin letters. 34 35 The third line is a string $t$ ($|t| = m$), consisting only of lowercase Latin letters. 36 37 Each of the next $q$ lines contains two integer numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the arguments for the $i$-th query. 38 39 Output 40 41 Print $q$ lines — the $i$-th line should contain the answer to the $i$-th query, that is the number of occurrences of string $t$ in a substring $s[l_i..r_i]$. 42 43 Examples 44 45 Input 46 47 ``` 48 10 3 4 49 codeforces 50 for 51 1 3 52 3 10 53 5 6 54 5 7 55 ``` 56 57 Output 58 59 ``` 60 0 61 1 62 0 63 1 64 ``` 65 66 Input 67 68 ``` 69 15 2 3 70 abacabadabacaba 71 ba 72 1 15 73 3 4 74 2 14 75 ``` 76 77 Output 78 79 ``` 80 4 81 0 82 3 83 ``` 84 85 Input 86 87 ``` 88 3 5 2 89 aaa 90 baaab 91 1 3 92 1 1 93 ``` 94 95 Output 96 97 ``` 98 0 99 0 100 ``` 101 102 Note 103 104 In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.