You are given a text and a pattern. Scan the text from left to right and greedily match the pattern: whenever the pattern is found starting at the current position, count it and jump forward past the whole matched block (so matches never overlap); otherwise advance by one position. Print how many non-overlapping matches you collect.
Because the scan is left-to-right and greedy, the count is uniquely determined. For instance, in aaaa the pattern aa matches at positions 0 and 2 for a count of 2 (it does not also count the overlapping match at position 1).
Input format
Line 1: the text, a string of lowercase English letters. Line 2: the pattern, a non-empty string of lowercase English letters.
Output format
A single integer: the number of non-overlapping, left-to-right greedy matches of the pattern in the text.
Constraints
- 1 <= length of text <= 100000.
- 1 <= length of pattern <= length of text.
- Both strings contain only lowercase letters
a-z.