codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.