link for author soln is https://s3.amazonaws.com/codechef_shared/download/Solutions/JUNE18/setter/SHKSTR.cpp
The author has used a solution which looks similar to this solution using tire .Have a note of the ascii values of ‘|’ & ‘_’ before looking into it
[https://www.codechef.com/viewsolution/18782372]
1 Like
Which part is unclear to you?
The addString function is kind of straightforward, although over-concisely done xD. The ptr variable is nothing but the node number. He is traversing the already added strings and adding character/nodes wherever applicable.
The query function is also simple. He will first traverse the try to min(S.length(),Trie'sPathLength). If he didnt end up at a leaf node, he will go for the lexicographically smaller one. In simpler words, what he is doing is as
- If current character is in trie - Add it to ans and check for next one in children
- If the character is not present (or if entire string is found), break out and print lexicographically smallest (t.fin tells that a string ends with this character/node)
Theres actually nothing else to explain xD. What part is unclear to you?
1 Like
this link is not working