Untitled

[Problem Description]


You are required to implement a feature named autocomplete which predicts the rest of a word a user is typing.


 


To implement this feature, all words are collected whenever they are input by the user.


The same word can be input several times by the user.


 


Words can be banned if the user does not want them to be recommended.


 


Utilize collected information and implement autocomplete which automatically completes a word according to rules when the user inputs the front part of the word.


Refer to the below API description for the rules of selecting words to be completed.


 


Implement each required function by referring to the following API description.


※ The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.


 


The following is the description of API to be written in the User Code.


void init()

This function is called in the beginning of each test case.

void inputWord(char mWord[20])

The number of inputting mWord increases by 1.

 

Parameters

   mWord : Word input by the user

int recommend(char mUser[20], char mAnswer[20])

The front part of a string is given as mUser.

This function selects a word according to the rules below, stores it in mAnswer, and then returns its length.

 

Words to be stored in mAnswer are selected according to the following rules:

1.     They must start with mUser and be included in the list of the words that have been input by inputWord().

2.     Among the words satisfying 1., select a word that has been input the most.

3.     If more than one word satisfies 2., select the most recently input word among them.

4.     If no words satisfy the above-mentioned rules, store mUser in mAnswer as it is.

 

To be recommended by recommend(), words must never been called by banWord() before.

Words banned by banWord() are not provided as mUser.

 

Parameters

   mUser : Front part of a word input by the user

   mAnswer : String where the result of the function needs to be stored

 

Returns

   This function returns the length of a string stored in mAnswer which is the array given as a parameter

void banWord(char mWord[20])

The user does not want mWord to be recommended.

Then, mWord must not be recommended by recommend() which is called later in the current test case. 

 

It is guaranteed that mWord has not been called before by banWord().

mWord may not have been called before by inputWord().

mWord can still be given to inputWord(), but

it must not be recommended by recommend().  

 

Parameters

   mWord : Word banned by the user


 


[Example]


Think of the following case in [Table 1].


Order

Function

Return Value

Ref.

1

init()

 

 

2

inputWord(mWord=”string”)

 

 

3

inputWord(mWord=”strong”)

 

 

4

inputWord(mWord=”string”)

 

 

5

inputWord(mWord=”strike”)

 

[Table 2]

6

recommend(mUser=”stri”)

6, answer=”string”

 

7

recommend(mUser=”stro”)

6, answer=”strong”

 

8

inputWord(mWord=”strike”)

 

[Table 3]

9

recommend(mUser=”st”)

6, answer=”strike”

 

10

recommend(mUser=”stra”)

4, answer=”stra”

 

11

banWord(mWord=”strike”)

 

 

12

recommend(mUser=”st”)

6, answer=”string”

 

13

banWord(mWord=”stress”)

 

 

14

inputWord(mWord=”stress”)

 

 

15

inputWord(mWord=”stress”)

 

 

16

inputWord(mWord=”stress”)

 

 

17

inputWord(mWord=”str”)

 

[Table 4]

18

recommend(mUser=”str”)

6, answer=”string”

 

19

recommend(mUser=”stre”)

4, answer=”stre”

 


                                                            [Table 1]


[Table 2] shows the number of times each word is input and their respective last input timings after Order 5.


 


rank

word

input count

last input

1

“string”

2

Order 4

2

“strike”

1

Order 5

3

“strong”

1

Order 3


                                                            [Table 2]


 


At Order 6, the highest-ranked word needs to be selected among the words in [Table 2] which start with “stri.”  


Therefore, between the words “string” and “strike,” “string” is stored in mAnswer, and 6, its length, is returned.


At Order 7, the highest-ranked word needs to be selected among the words in [Table 2] which start with “stro.”


Since “strong” is the only word in [Table 2] which starts with “stro,” the word is stored in mAnswer, and 6, its length, is returned.


 


[Table 3] shows the number of times each word is input and their respective last input timings after Order 8.


rank

word

input count

last input

1

“strike”

2

Order 8

2

“string”

2

Order 4

3

“strong”

1

Order 3


                                                            [Table 3]


 


At Order 9, the highest-ranked word needs to be selected among the words in [Table 3] which start with “st.”


Therefore, among the words “strike”, “string”, and “strong,” “strike” is stored in mAnswer, and 6, its length, is returned.


The words “strike” and “string” are input the same number of times, but “strike” has the last input timing later than that of “string.” Therefore, “strike” is selected.


 


At Order 10, the highest-ranked word needs to be selected which starts with “stra” among the words in [Table 3].   


Since there is no such word, “stra” is stored in mAnswer as it is, and 4, its length, is returned.


 


At Order 11, the word “strike” is banned.


Order 12 asks the same question as Order 9.


Since “strike” is a banned word, the highest-ranked word needs to be selected among the words except for “strike.”


Therefore, between the words “string” and “strong,” “string” is stored in mAnswer and 6, its length, is returned.   


 


At Order 13, the word “stress” is banned.


[Table 4] below shows the number of times each word is input and their respective last input timings after Order 17.


Since “strike” and “stress” are banned, they are not recommended by recommend().


rank

word

# of input

last input

1

“stress”

3

Order 16

2

“strike”

2

Order 9

3

“string”

2

Order 4

4

“str”

1

Order 17

5

“strong”

1

Order 3


                                                            [Table 4]


 


At Order 18, the highest-ranked word needs to be selected among the words in [Table 4] which start with “str” except for “stress” and “strike.”


As a result, “string” is stored in answer, and 6, its length, is returned.


 


At Order 19, the highest-ranked word needs to be selected among the words in [Table 4] which start with “stre” except for “stress” and “strike.”


Since there is no word starting with “stre” among the unbanned words in [Table 4], “stre” is stored in answer as it is and 4, its length, is returned.


 


 [Constraints]


1. The function init() is called in the beginning of each test case.


2. All input words consist of lowercase alphabet letters of less than 20 letters including the null character.


3. If a word once has been provided as mWord in banWord(), it is not provided as mWord in banWord() and as mUser in recommend().


4. For each test case, the sum of calls of the all functions is up to 100,000.


5. For each test case, the number of types for mWord, which is called by both inputWord() and banWord(), is up to 25,000.


 


[Input and Output]


As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.


 


The below is the correct output for the sample input.


#1 100

#2 100

#3 100

#4 100

#5 100