Counting Overlapping Substring Occurrences

Given a string s and a substring pattern, your task is to count the number of times that pattern occurs in s, including the overlapping occurrences.

For example, in the string ababababa with the pattern aba, the pattern appears 4 times (positions 0, 2, 4, and 6 considering 0-based indexing). Similarly, in the string aaaaa with the pattern aa, there are 4 occurrences, each overlapping with the previous one.

The formula for the number of overlapping occurrences can be given in \(\LaTeX\) as follows:

[ \text{result} = \sum_{i=0}^{|s|-|pattern|} \mathbf{1}_{{s[i:i+|pattern|] = pattern}}, ]

where \(\mathbf{1}_{\{condition\}}\) is an indicator function that is 1 if the condition is true, and 0 otherwise.

inputFormat

The input consists of two lines.

• The first line is the string s.
• The second line is the substring pattern.

outputFormat

Output a single integer, which is the number of times the substring pattern occurs in s (including overlapping occurrences).

## sample

ababababa
aba

4

</p>