Rearrange

In particular, he has a string \(s\) and a favorite string \(t\). Both \(s\) and \(t\) consist of lowercase Latin letters. He wants to rearrange the characters of \(s\) to form a new string \(p\). The way Tiger rearranges the characters of \(s\) to form \(p\) is by iterating over the characters of \(s\) from left to right and adding each character to either the front or the back of \(p\) (which is initially empty).

He wants you to tell him the maximum number of times \(t\) can appear as a substring in \(p\). You will have to answer \(q\) independent test cases.

C++: 2.5 seconds

Java, Python: 5 seconds

Memory Limit: 256mb

\((1 \leq |t| \leq |s| \leq 200)\)

It is guaranteed that the sum of \(|s|\) over all test cases does not exceed \(200\).

The first line of each test case has the string \(s\) .

The second line of each test case has the string \(t\) .

bca

bca

acbebca

bca

cba

bca

2

1

Credit: Eggag