递归子串计数

题目背景

在字符串处理的场景中，我们经常需要查找某个特定模式出现的次数。有时，这些模式不能相互重叠，并且我们希望通过递归的方式来解决这个问题。

题目描述

给定一个字符串和一个非空子串 sub，递归计算 sub 在字符串中不重叠出现的次数。

输入格式

输入以如下格式从标准输入中给出。

第一个字符串 $S$ 字面量 " " 第二个字符串 $SUB$

输出格式

输出以如下格式输出到标准输出中。

一个整数，表示子串 sub 在字符串中不重叠出现的次数。

样例

catcowcat" "cat

2

catcowcat" "cow

1

catcowcat" "dog

0

样例解释

样例 1: 字符串为 "catcowcat"，子串为 "cat"。 第一个 "cat" 出现在索引 0。 第二个 "cat" 出现在索引 6。 它们不重叠，因此出现次数为 2。

样例 2: 字符串为 "catcowcat"，子串为 "cow"。 "cow" 只出现一次，在索引 3。 因此出现次数为 1。

样例 3: 字符串为 "catcowcat"，子串为 "dog"。 "dog" 没有在字符串中出现。 因此出现次数为 0。

数据范围

每个测试用例的时间限制为 1 秒，内存限制为 1024 KiB。