Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 2737
Occurrence

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given a string A which can be represented as A1A2..An (n is the length of A) and a string B which can be represented as B1B2..Bm (m is the length of B), you will need to find the occurrence of B from A.

The definition of occurrence is as follows:
If there exists an index p (p >= 1 and p + m <= n), and ApAp+1..Ap+m-1 matches with any rotation of B (B1B2..Bm-1Bm, B2B3..BmB1, ��, BmB1..Bm-2Bm-1 are all the rotation of B), we call it is an occurrence of B from A.

Input:

This problem contains multiple test cases. Each test case contains two lines, which are the strings A and B. The length of A is not greater then 1000 and the length of B is not greater than 100. All the strings are only consist of lowercase letters.

Output:

Each test should output an integer indicating the occurrence of B from A in a single line.

Sample Input:
```abab
ab
aaaa
a
aaaa
aa
```
Sample Output:
```3
4
3
```

Author: JIN, Tianpeng
Source: Zhejiang Provincial Programming Contest 2006, Preliminary
Submit    Status