Count Non-Overlapping Occurrences

Given two strings s and p, your task is to count the number of non-overlapping occurrences of the pattern p in the string s.

More formally, you need to determine the maximum number of disjoint occurrences of p in s. An occurrence is valid only if it does not share any characters with another occurrence.

For example, if s = "ababa" and p = "aba", there is only 1 valid occurrence as the potential second occurrence would overlap with the first.

Note: You should read input from stdin and output the result to stdout.

inputFormat

The input consists of two lines:

• The first line contains the string s.
• The second line contains the pattern string p.

Both strings are non-empty and may contain any visible characters.

outputFormat

Output a single integer that represents the number of non-overlapping occurrences of the pattern p within the string s.

ababa
aba

1