Many programmers use
CamelCase when naming variables, functions, classes and other entities. In CamelCase, when a name consists of multiple words concatenated together, such as
myawesomevariablename, the first letter of every distinct word is capitalized. Sometimes there is more than one way to turn a string of letters into CamelCase.
In Lower CamelCase the first word is the only word not capitalized, whereas in Upper CamelCase all of the words are capitalized.
The input will contain a dictionary, followed by ~10~ test cases.
The dictionary starts with an integer ~N~ where ~(1 \le N \le 2 \times 10^5)~ followed by ~N~ lines, each containing a word.
A word consists of a string of lowercase English letters and the apostrophe character
Each of the ~10~ lines following the dictionary will contain a single test case. Each test case consists of a string of lowercase English letters of length ~2000~ or less, created by concatenating words from the dictionary.
Your program should output ~10~ integers (one per line), representing the minimum number of capitalizations required to convert each test word to Lower
CamelCase, so that it can be read as a string of legal words from the dictionary.
Note that the sample input below contains only ~4~ test cases, but the real data files will contain ~10~.
26 aid all app apple brown come country crab crabapple dogs for fox good is jumps lazy men now of orchard over quick the their time to apple appleorchard crabapple thequickbrownfoxjumpsoverthelazydogs
0 1 0 8
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org