Substring search P79329


Statement
 

pdf   zip

html

You are given a string s and many short patterns, all of the same length. The string s and the patterns are composed only of ‘a’ and ‘b’ characters. For every given pattern, you must tell how many times it is included in s. Can you do it efficiently, both in time and in space?

Input

Input starts with a number t, followed by t cases. Each case begins with a non-empty string s, followed by a number p ≥ 1, followed by p non-empty patterns. The only characters in s and in the patterns are ‘a’ and ‘b’. The length of s is at most 106. All the patterns of the same case have the same length, which is at most 60. No given pattern is longer than s.

Output

For every case, print the case number starting at 1 followed by the number of times that each given pattern is included in s. Print a blank line after every case.

Public test cases
  • Input

    2
    
    aabaaaabaaab
    3
    aaba
    aaaa
    baab
    
    bbbbbbbb
    1
    bb
    

    Output

    Case 1:
    2
    1
    0
    
    Case 2:
    7
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Quart Concurs de Programació de la UPC - Final
    Date
    2006-10-04