Scribd
Upload
6 views1 page

Problem (Substring Frequency)

Uploaded by

itsmeachol
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

Problem (Substring Frequency)

Uploaded by

itsmeachol
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Rising Star Programming Contest 2.

0 Sep 30, 2024

Problem B. Substring Frequency


Time limit 1000 ms
Mem limit 65536 kB

A string is a finite sequence of symbols that are chosen from an alphabet. In this problem,
you are given two non-empty strings A and B, both contain lower case English alphabets.
You have to find the number of times B occurs as a substring of A.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with two lines. First line contains A and second line contains B. You can

assume than 1 ≤ length(A),length(B) ≤ 106.

Output

For each case, print the case number and the number of times B occurs as a substring of B.

Sample
Input Output

4 Case 1: 0
axbyczd Case 2: 4
abc Case 3: 2
abcabcabcabc Case 4: 5
abc
aabacbaabbaaz
aab
aaaaaa
aa

Note

Dataset is huge, use faster I/O methods.

You might also like