Challenges
Please select a challenge
Problem Statement
Mr. Alice has given an assignment to his students. The students are given long words. They have to find out the maximum number of words a given word can be split into, such that the resulting words all form legitimate words contained in a given dictionary. The broken up words must be continuous in the parent word. See example for clarification.
For example, the string AMANGO can be split as {A, MANGO}, {A, MAN, GO} and {AM, AN, GO}, wherein, each of the resulting words is contained within the dictionary {A, AM, AN, GO, MAN, MANGO}, here the final set of split up words does not produce any word that is not contained in the dictionary.The students are having a tough time completing this assignment. They cannot even copy it as not a single person has been able to do it. Help them out.
Input
First line contains T, number of test cases. Next line contains the String, N that has to be divided into words. Next line contains, L the number of words in the dictionary. Next L line contains L words.
Output
For each test case output the maximum number of words that can be generated from the string.
Constraints
1 <= T <= 25
1 <= N, L <= 1500
Sample Input
2 amantentononewitheel 19 a an am ant ent tent man ten on one ton no none new with the he heel wit amango 5 a am an man go
Sample Output
7 3
Dcoded By: Saurav Chandra
Solved By: 159
Maximum Marks: 15