Document Search

Interview

Time limit2sMemory limit128 MB

Summary

Given a document and a word, find the maximum number of non-overlapping occurrences of the word within the document.

Level: Medium4 of 10
Topics: String matching, Greedy, Dynamic programming
Solved: No attempts yet

Problem

You want to count how many times a word appears in a document made only of lowercase English letters and spaces. However, two counted occurrences must not overlap, even by one character.

For example, if the document is abababa and the word is ababa, the word can start at position 0 or at position 2. These two occurrences overlap, so they cannot both be counted.

Given the document and the word to search for, compute the maximum number of non-overlapping occurrences of the word.

Input

The first line contains the document. Its length is at most 2500.

The second line contains the word to search for. Its length is at most 50.

The document and the word consist only of lowercase English letters and spaces.

Output

Print the maximum number of times the word can appear in the document without overlapping.

Examples4

Example 1
Input
```
ababababa
aba
```
Expected output
```
2
```
Example 2
Input
```
a a a a a
a a
```
Expected output
```
2
```
Example 3
Input
```
ababababa
ababa
```
Expected output
```
1
```
Example 4
Input
```
aaaaaaa
aa
```
Expected output
```
3
```