ACRYM2 - Acronym II
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. Since the answer can be large, output the answer modulo 1000000007.
Note: This is a harder version of the problem ACRYM, with larger constraints. Please read the input section carefully.
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| ≤ 50000)
Following N lines, each consisting of one string Wi. (1 ≤ |Wi| ≤ 250)
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
Rishav Goyal:
2020-09-21 19:56:40
Hi @Blue Mary and @Suhash,
|
|
ajay_pal_11:
2020-06-19 06:52:00
so, is there a better way to pre-process ??
|
|
ajay_pal_11:
2020-06-18 19:12:18
@suhash is this was the intended solution or i need to optimise something ??
|
|
Scape:
2020-06-09 20:34:28
What does it mean to either skip or use the conjunction and adpositions? How does this change the answer?
|
|
[Rampage] Blue.Mary:
2020-06-08 03:25:11
After constraints change my program becomes very heavy & ugly...
|
|
suhash:
2020-06-07 20:33:35
Constraints (and test data) have been updated as the constraints on the easier version are not going to be changed (https://www.spoj.com/problems/ACRYM/). Since there was only one successful submission (@BlueMary), I discarded all the previous solutions. Please re-submit. Really sorry for the inconvenience. Last edit: 2020-06-08 06:23:36 |
Added by: | suhash |
Date: | 2020-06-07 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | ACRYM |