ACRYM - Acronym
An acronym is made of up the initial letter(s) of the words in a phrase, such as EU (European Union) and BREXIT (BRitish EXIT). In this problem, we can also either ignore or consider the conjunction "and", and the following adpositions "in", "on", "at", "to", "of", "from", "for" and "with" when making the acronym, such as BENELUX (BElgium, NEtherlands and LUXembourg) and RADAR (RAdio Detection And Ranging).
Given an acronym A, and a list of N strings W1, W2 ... WN, you would like to find out the number of possible combinations of making the given acronym by using all the N strings following their order. That is, the acronym must be made up of at least one initial letter of each word, except the above-mentioned conjunction and adpositions (either skip or use it). Both A and the N strings only consist of lowercase latin letters.
Input
The first line is the number of test cases T. (1 ≤ T ≤ 20)
For each test case, it starts with one integer N. (1 ≤ N ≤ 200)
Next line is a string A. (1 ≤ |A| ≤ 104)
Following N lines, each consisting of one string Wi. (1 ≤ |Wi| ≤ 50)
It is guaranteed that W1 is neither conjunction nor adposition.
Output
Output one integer indicating the number of possible combinations.
Example
Input: 3 3 duckhim duck hello moto 7 natiofforessaa national office for forest safety in aachen 4 whiskey what is secret key Output: 0 4 1
Explanation
In case 1, no combination is possible.
In case 2, there are four possible combinations:
- NATIonal OFfice for FORESt SAfety in Aachen
- NATIonal OFfice for FORESt Safety in AAchen
- NATIonal Office For FORESt SAfety in Aachen
- NATIonal Office For FORESt Safety in AAchen
In case 3, only one possible combination exists:
- WHat Is Secret KEY
hide comments
suhash:
2020-06-07 14:50:32
Since there is no update from the author, I created a new problem with better test data: https://www.spoj.com/problems/ACRYM2/
|
|
suhash:
2020-05-26 14:30:54
Nice problem, but the test cases are weak. Currently, the answer fits in a signed 32 bit integer. Issues with the current version:
|
Added by: | him0727 |
Date: | 2020-05-14 |
Time limit: | 0.400s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own problem |