#86Medium
How many times a substring occurs
Time: 1 s · Memory: 256 MB
- Strings
Statement
You are given two strings and . Find how many times occurs in . Occurrences may overlap: aa occurs three times in aaaa (starting at positions 1, 2 and 3).
Input format
The first line contains and the second line contains , each of to ASCII characters. has no spaces, may have them.
Output format
A single integer — the number of occurrences.
Examples
Input
abababa aba
Output
3
Input
salom dunyo o
Output
2
Note
For every position of compare the piece of length with . In the first example aba starts at positions 1, 3 and 5 — the answer is . If is longer than , the answer is .
