LCC '22 Contest 6 J4 - LCC Word Hunt

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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 i, i+k, i+2k,..., i+nk of the string, where i and k are positive integers.

LBYYOUNVS

In the above string, the word LYONS is embedded as its characters are at indices 1 (L), 3 (Y), 5 (O), 7 (N), and 9 (S). Thus, i=1 and k=2.

Also in the above string, the word YOU is embedded at indices 4-6, where i=4 and k=1.

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 S, a list of words of length N, and wants you to change up to one character in S 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 1-30 characters long and only contain uppercase latin characters (A-Z). Each string in Shane's list is distinct.

1 \le N \le 10^3 and will not exceed the number of distinct possible strings embedded in S.

Input Specification

The first line will contain the string S. The next will contain the integer N, followed by N 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 S.

Sample Input

LBYYOUNVS
3
LYONS
YOUNG
BRUV

Sample Output

2

Explanation for Sample Output

If we change the V at index 8 to a G, YOUNG is embedded at indices 4-8. LYONS is still embedded with this change, but BRUV is not.

If we change the Y at index 4 to a R, BRUV is embedded at indices 2, 4, 6, and 8. 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

There are no comments at the moment.