Consider the following simple auto complete feature. When you type some characters in the google text bar, the search engine automatically gives best visited and matching result among it’s database. You are given an incomplete search text, output the best search result.
Each Word in search engine has weight attached to it also called priority factor. The more the weight , the high is the priority factor. You are given a set of strings for searching from the database and print the maximum priority of it from the database.
The first line contains the database entries and number of search queries i.e n and q.
The next n lines contains a string ‘S’ and weight ‘w’ which are the databases and the priority factor if it.
The next q lines follow a string ‘t’ which the user will enter to search.
Output the ‘q’ lines in which each line have a string ‘t’ with the maximum priority factor.
N >=1, weight >=0
length (s) >= 10^6
(Hint:- The Structure of the trie node will include a one more variable weight other than the bool ENDOFWORD and char APLHABETS. )
Programming language 10