Problem V
Bless You Autocorrect!
The autocorrect feature on Jenny’s phone works like this: the phone has an internal dictionary of words sorted by their frequency in the English language. Whenever a word is being typed, autocorrect suggests the most common word (if any) starting with all the letters typed so far. By pressing tab, the word being typed is completed with the autocorrect suggestion. Autocorrect can only be used after the first character of a word has been typed – it is not possible to press tab before having typed anything. If no dictionary word starts with the letters typed so far, pressing tab has no effect.
Jenny has recently noticed that it is sometimes possible to use autocorrect to her advantage even when it is not suggesting the correct word, by deleting the end of the autocorrected word. For instance, to type the word “autocorrelation”, Jenny starts typing “aut”, which then autocorrects to “autocorrect” (because it is such a common word these days!) when pressing tab. By deleting the last two characters (“ct”) and then typing the six letters “lation”, the whole word can be typed using only $3$ (“aut”) ${}+1$ (tab) ${}+2$ (backspace twice) ${}+6$ (“lation”) $= 12$ keystrokes, $3$ fewer than typing “autocorrelation” without using autocorrect.
Given the dictionary on the phone and the words Jenny wants to type, output the minimum number of keystrokes required to type each word. The only keys Jenny can use are the letter keys, tab and backspace.
Input
The first line of input contains two positive integers $n$ ($1 \le n \le 10^5$), the number of words in the dictionary, and $m$ ($1 \le m \le 10^5$), the number of words to type. Then follow $n$ lines with one word per line, sorted in decreasing order of how common the word is (the first word is the most common). No word appears twice in the dictionary. Then follow $m$ lines, containing the words to type.
The dictionary and the words to type only use lower case letters ‘a’-‘z’. The total size of the input file is at most $1$ MB.
Output
For each word to type, output a line containing the minimum number of keystrokes required to type the corresponding word.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 5 austria autocorrect program programming computer autocorrelation programming competition zyx austria |
12 4 11 3 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 yogurt you blessing auto correct bless you autocorrect |
5 3 9 |
