Challenges

Bitwise for Dummies
This is to provide you with an introductory experience of bit-wise ope...
Max. Marks: 6
Solved By : 818
Double the Number
Given an array A of size N and K. count all the number of elements suc...
Max. Marks: 8
Solved By : 905
Rotate Array
You are given an array of N length. You have to rotate the array right...
Max. Marks: 6
Solved By : 1927
Floating Number
Bob has a floating point number N. He wants to set the precision for 2...
Max. Marks: 4
Solved By : 5572
SwapMaster solves Symmetric Swap
The SwapMaster is known to be the greatest and fastest swapper of all ...
Max. Marks: 4
Solved By : 4382
String Matching
Cody has a sequence of characters N. He likes a sequence if it contain...
Max. Marks: 3
Solved By : 2531
Leap Year
Steve is playing a quiz game with his brother John. As Steve just lear...
Max. Marks: 6
Solved By : 3948
Project Teams
There are N students in a class and Teacher want to divide these stude...
Max. Marks: 5
Solved By : 4561
Circle of Numbers
All numbers in NumberLand are standing in a circle for a dancing cerem...
Max. Marks: 6
Solved By : 3127
Happy String
A happy string is a string in which each character is lexicographicall...
Max. Marks: 4
Solved By : 2367
Alice and Dictionary
loading...
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