We (the LCC team) would like to help ease the stress of AP exams by providing you a fun word hunt!
In the LCC Word Hunt, words are embedded in a string. A word is considered to be in a string if its characters are at indices of the string, where and are positive integers.
LBYYOUNVS
In the above string, the word LYONS
is embedded as its characters are at indices (L
), (Y
), (O
), (N
), and (S
). Thus, and .
Also in the above string, the word YOU
is embedded at indices , where and .
By regular rules, you are given a list of words to find embedded in the string. However, of course, Shane thinks the word hunt is too boring. He gives you a string , a list of words of length , and wants you to change up to one character in so that the number of distinct words in the list embedded in the string is maximized. Can you determine the maximum number of distinct words that can be embedded under his rule?
Constraints
All strings will be characters long and only contain uppercase latin characters (A-Z
). Each string in Shane's list is distinct.
and will not exceed the number of distinct possible strings embedded in .
Input Specification
The first line will contain the string . The next will contain the integer , followed by lines containing a string that is in Shane's list of words.
Output Specification
Output the maximum number of distinct words that can be embedded in the string given up to one character change to .
Sample Input
LBYYOUNVS
3
LYONS
YOUNG
BRUV
Sample Output
2
Explanation for Sample Output
If we change the V
at index to a , YOUNG
is embedded at indices . LYONS
is still embedded with this change, but BRUV
is not.
If we change the Y
at index to a , BRUV
is embedded at indices , , , and . LYONS
is still embedded with this change, but YOUNG
is not.
It can be proven that it is impossible to embed all three words with one character change.
Comments