Recursive Substring Count

Background

In string processing scenarios, we often need to find the number of occurrences of a specific pattern. Sometimes, these patterns cannot overlap, and we want to solve this problem recursively.

Problem Description

Given a string and a non-empty substring sub, compute recursively the number of times that sub appears in the string, without the substrings overlapping.

Input Format

Input is given from Standard Input in the following format.

The first string $S$ The literal string " " The second string $SUB$

Output Format

Output to Standard Output in the following format.

An integer representing the number of non-overlapping occurrences of the substring sub in the string.

Sample

catcowcat" "cat

2

catcowcat" "cow

1

catcowcat" "dog

0

Sample Explanation

Sample 1: The string is "catcowcat\