Count Pattern Occurrences

Difficulty: 1300 2000 ms 128 MB

strings

Count the occurrences of pattern P inside text T. Occurrences may overlap: aaa contains aa twice.

Input: the first line has T; the second line has P.

Output: the number of (possibly overlapping) occurrences of P in T.

Constraints:

• 1 ≤ |T| ≤ 10⁴
• 1 ≤ |P| ≤ |T|
• lowercase letters

Sample Tests

aaa
aa

2

ababab
ab

3

Read the Editorial