Fluffy and Typing Password
All submissions for this problem are available.
Fluffy the Squirrel is trying to login to his Codechef account. He knows a list of n passwords. If he enters any of these passwords, he will be able to log in to Codechef. He has already typed a string s. However, Flippy the Bird invited him to play a game of tag outside and after playing, he had to continue typing the password. However, he might've made some mistakes while typing the password so he might need to delete some letters and type the correct letters. Formally, he can hit the Backspace key, which takes 1 second and removes the last letter that he has typed (it doesn't do anything if he didn't type anything). He can also type any of the lowercase letters, which also takes 1 second (per letter). You're given q possible string s that Fluffy has typed before he went to play. For each such string, output the minimum number of seconds needed for Fluffy to type one of the n valid passwords.
The first line of the input contains a single integer n, the number of valid passwords. The next n lines contain a string of lowercase letters, each denoting a valid password. The next line contains a single integer q, the number of query strings. The next q lines contain a string of lowercase letters, denoting a query string.
Output q lines with one integer each, the minimum number of seconds needed to type a valid password if Fluffy has typed the i-th string before he went to play.
- 1 ≤ n ≤ 500000
- 1 ≤ Sum of length of valid passwords ≤ 500000
- 1 ≤ q ≤ 500000
- 1 ≤ Sum of length of query strings ≤ 500000
- Subtask 1 (27 points) : 1 ≤ n, q, Sum of length of valid passwords, Sum of length of query strings ≤ 5000, Time limit = 1 second. .
- Subtask 2 (73 points) : Original Constraints
Input: 3 abc absicca fluffy 2 flux abacus Output: 4 5
Example case. Fluffy can type the word "fluffy" from "flux" in 4 seconds (backspace -> 'f' -> 'f' -> 'y') and the word "abc" from "abacus" in 5 seconds (backspace -> backspace -> backspace -> backspace -> 'c').
|Tags||easy-medium, mco1602, trie, zscoder|
|Time Limit:||0.25 - 1 sec|
|Source Limit:||50000 Bytes|
|Languages:||CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.