Alice and Bob play Contact
All submissions for this problem are available.
Chef Alice and Chef Bob are going to play their version of the social word game called Contact. First things first, let's say that the vocabulary of Alice and Bob are defined by English words A1, A2, ..., AN and B1, B2, ..., BM, respectively. Also, we define Prefix(S, i) as prefix of string S consisting of first i characters. We define |S| as length of string S.
Before the game starts Alice tells Bob a word Ai from her vocabulary. The game proceeds as follows:
- In the first move, Bob tells a word P from his vocabulary such that Prefix(P, 1) == Prefix(Ai, 1).
- In second move, Bob tells a word P (which shouldn't have been used before by him) from his vocabulary such that Prefix(P, 2) == Prefix(Ai, 2).
- In the jth move, Bob tells a word P (which wasn't used earlier by him) from his vocabulary such that Prefix(P, j) == Prefix(Ai, j).
- The game ends when Bob has made |Ai| moves or Bob fails to make a move.
Bob is secretly aware of Alice's whole vocabulary and also, he wants to spend as much time possible with her. Now, they'll play this game for all the N words in Alice's vocabulary. Note that all games are independent. You have to tell Bob what is the sum of maximum number of moves he can make for each of the N games.
The first line of the input contains integers N and M denoting the size of vocabularies of Alice and Bob, respectively.
Next N + M lines contain strings A1, A2, ..., AN and B1, B2, ..., BM, each in a separate line.
Output the sum of maximum number of moves for each of the N games (i.e. if Alice and Bob play the game for each word in Alice's vocabulary).
- 1 ≤ N, M ≤ 105
- 1 ≤ |Ai|, |Bi| ≤ 105
- 1 ≤ Sum of lengths of Ai and Bi for all i ≤ 106
- All strings consist of English lowercase alphabets.
- All strings in array A are distinct.
- All strings in array B are distinct.
Input: 3 2 ac abd b ae bd Output: 3
Alice choses word "ac". Bob can make a maximum of 1 move. In first move, Bob tells "ae". Now Bob can't make any more moves.
Alice choses word "abd". Again, Bob can make a maximum of one move by telling the word "ae".
Alice choses word "b". Again, Bob can make a single move in which he tells the word "bd". Game ends here because Bob cannot make more than |Ai| moves.
So, you can see that total number of moves Bob can make is 1 + 1 + 1 = 3.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.