ZOJ Problem Set - 3239
As a Linux user, Whistler has tried several command-line shells. Among these shells, he likes the Z Shell('ZSH' for short) best because ZSH provides more amazing features.
Command-line shells usually provide some completion feature. For example, in the directory '/home/whistler', there is only a file named 'document'. Then you can type '/home/whistler/d' and press [TAB] to let the shell complete the word 'document'.
ZSH makes completion more enjoyable, especially for lazy guys. Completion in ZSH can be done using first several letters in each directory. Consider the same situation above, '/home/whistler/document' could be completed using '/h/wh/d' and a single [TAB], if there are no other files or directories with a full path of '/h*/wh*/d*'.
Unfortunately, there is no ZSH on a remote system used by Whistler. And Whistler does not have enough permission to install ZSH on that system. So he asks you to implement a simple completion program.
To simplify the problem, there are several assumptions:
This problem contains multi test cases (no more than 4). Please proceed to the end of input.
The 1st line only contains an integer N (0 <= N <= 10000).
Following N lines are full paths of directories or files, one per line. It is guaranteed that full path of a directory occurs before files or directories it contains occur. (that is, '/blabla' occurs before any '/blabla/foo' occurs, where 'blabla' may contain one or more '/')
The N+2 line only contains an integer M (0 <= M <= 30000).
Following M lines are inputs by users, one per line.
There is a blank line after each test case.
Note that the largest test case is generated randomly, not from an existing file system.
For each user input, if there is a unique completion, output that completion in one line, without tailing '/'. When there is more than one way or no way to complete, output an integer, which is the count of possible completions in one line.
5 /usr /usr/local /home /home/whistler /home/who 5 /u /home /u/loc /ho/w /bin
/usr /home /usr/local 2 0
Author: WU, Jun
Source: ZOJ Monthly, August 2009