Excuses, Excuses!
InterviewTime limit1sMemory limit128 MB
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, (), is the number of keywords to search for. The second, (), is the number of excuses in the set. The next lines each contain exactly one keyword. The following lines each contain exactly one excuse.
Every keyword consists only of contiguous lowercase alphabetic characters of length () and occupies columns through 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 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 ). 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.