Longest Dictionary Word

Given a string S and a list of words (dictionary), find the longest word in the dictionary that can be formed by deleting some characters of S without changing the relative order of the remaining characters. If there is more than one possible result, return the one that is lexicographically smallest among those of maximum length. If no word in the dictionary can be formed, return an empty string.

The problem can be solved by checking each word in the dictionary to see if it is a subsequence of S. A common approach is to sort the dictionary by descending length and then lexicographical order and choose the first valid word.

Note: All input and output operations must be performed via standard input (stdin) and standard output (stdout).

inputFormat

The input is read from standard input and is structured as follows:

• The first line contains the string S.
• The second line contains an integer N, the number of words in the dictionary.
• The following N lines each contain a word from the dictionary.

outputFormat

Output a single line to stdout: the longest word from the dictionary that is a subsequence of S. If no such word exists, output an empty string.

abpcplea
4
ale
apple
monkey
plea

apple