Under construction

Still being built. Things may change

Excuses, Excuses!

Interview

Time limit1sMemory limit128 MB

Summary
Find the excuses containing the most keyword occurrences, where keywords match case-insensitively and only as whole words.
Level

Medium4 of 10

Topics
String, Hash map, Implementation, Brute force
Solved
No attempts yet

Problem

A judge is frustrated by the flimsy excuses that people summoned for jury duty give in order to avoid serving. To cut down the time spent listening to silly excuses, write a program that searches a list of excuses for a list of keywords so it can flag the lame ones. Keywords are matched regardless of letter case.

Input

The input consists of several data sets. The first line of each set contains exactly two integers. The first, KK (1≤K≤201 \le K \le 20), is the number of keywords to search for. The second, EE (1≤E≤201 \le E \le 20), is the number of excuses in the set. The next KK lines each contain exactly one keyword. The following EE lines each contain exactly one excuse.

Every keyword consists only of contiguous lowercase alphabetic characters of length LL (1≤L≤201 \le L \le 20) and occupies columns 11 through LL of its line. An excuse may contain any uppercase or lowercase alphanumeric character, a space, or any of the punctuation marks ".,!? and is at most 7070 characters long. Every excuse contains at least one non-space character.

Input continues until the end of file.

Output

For each data set, print the worst excuse or excuses. The worst excuse is the one that contains the greatest number of keyword incidences. A keyword is counted as occurring in an excuse only when it appears in contiguous form and is bounded on each side by the start or end of the line, a space, or any non-alphabetic character. Each separate appearance of a keyword counts as one incidence.

Begin each data set's output with a line consisting of Excuse Set # immediately followed by the set number (starting at 11). On the following lines, print every worst excuse exactly as it was read in. When several excuses tie for the worst, print them in the order in which they appear in the input. Separate consecutive data sets with a blank line.

Examples3

  1. Example 1

    Input
    5 3
    dog
    ate
    homework
    canary
    died
    My dog ate my homework.
    Can you believe my dog died after eating my canary... AND MY HOMEWORK?
    This excuse is so good that it contain 0 keywords.
    6 5
    superhighway
    crazy
    thermonuclear
    bedroom
    war
    building
    I am having a superhighway built in my bedroom.
    I am actually crazy.
    1234567890.....,,,,,0987654321?????!!!!!!
    There was a thermonuclear war!
    I ate my dog, my canary, and my homework ... note outdated keywords?
    
    Expected output
    Excuse Set #1
    Can you believe my dog died after eating my canary... AND MY HOMEWORK?
    
    Excuse Set #2
    I am having a superhighway built in my bedroom.
    There was a thermonuclear war!
    
  2. Example 2

    Input
    2 3
    red
    blue
    The red car.
    A blue sky.
    Nothing here at all.
    
    Expected output
    Excuse Set #1
    The red car.
    A blue sky.
    
  3. Example 3

    Input
    1 1
    hi
    hi there
    1 2
    bye
    say bye now
    no match
    
    Expected output
    Excuse Set #1
    hi there
    
    Excuse Set #2
    say bye now