cho.shBless You Autocorrect!
For each target word, compute the fewest keystrokes using letter keys, tab (autocomplete to the most common dictionary word matching the typed prefix), and backspace.
Medium6TrieDynamic programmingStringNo attempts yetTime limit3sMemory limit512 MBProblem
Typing on a phone is tedious. Typos are easy to make, so most phones have an autocorrect feature. Autocorrect fixes common typos, and it also suggests how to finish the word you are typing. Jenny has been working out how to use that feature to her advantage, so that she can send a message with as little typing as possible.
Autocorrect on Jenny's phone works like this. The phone holds a dictionary of words sorted by how common they are in English. While a word is being typed, autocorrect suggests the most common dictionary word that starts with all the letters typed so far. Pressing tab completes the word being typed with that suggestion. Autocorrect can only be used after the first character of a word has been typed, so pressing tab before typing anything is not possible. If no dictionary word starts with the letters typed so far, pressing tab has no effect.
Jenny noticed that autocorrect can pay off even when it does not suggest the word she wants, because she can delete the end of the completed word. Say she wants to type "autocorrelation". She types "aut" and presses tab, which completes it to "autocorrect" (such a common word these days). Deleting the last two characters "ct" and then typing the six letters "lation" finishes the word in 3 ("aut") + 1 (tab) + 2 (two backspaces) + 6 ("lation") = 12 keystrokes, 3 fewer than typing "autocorrelation" without autocorrect.
Given the dictionary on the phone and the words Jenny wants to type, find the minimum number of keystrokes needed for each word. The only keys Jenny can use are the letter keys, tab and backspace.
Input
The first line contains two integers n (1≤n≤105), the number of words in the dictionary, and m (1≤m≤105), the number of words to type.
The next n lines contain one dictionary word each, in decreasing order of how common the word is. The first word is the most common. No word appears twice in the dictionary.
The next m lines contain the words to type, one per line.
The dictionary words and the words to type use only the lower case letters 'a' to 'z'. The total size of the input is at most 1 MB.
Output
For each word to type, print one line with the minimum number of keystrokes needed to type it.