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,
It would be really cool if the time limit is made in such a way that it checks time complexity of algorithm in terms of Big-O rather than extra optimizing the algorithm.
It would be cool to solve problem on SPOJ and also save us time, we have also solved it in correct time complexity as well (i.e. Big-o is optimal).

==(suhash)==>

@Rishav: The time limit is pretty relaxed and allows a wide range of algorithms (without needing constant optimisation). My solution has complexity O(|A| * (N + |Wi|)) per test case, while the best submission has complexity O(N * (|A| + |Wi|)) per test case. There are also solutions which have a log factor and they pass comfortably within the time limit. Please point me to your submission (if you think the complexity is correct) and I can take a look.

Last edit: 2020-09-26 10:24:41
ajay_pal_11: 2020-06-19 06:52:00

so, is there a better way to pre-process ??

RE: Added some tags to the problem now. The first part can be done using a trie (and building an automaton) by just pre-processing the first input string.

Last edit: 2020-06-24 17:09:03
ajay_pal_11: 2020-06-18 19:12:18

@suhash is this was the intended solution or i need to optimise something ??

RE: Your solution has the right complexity too. Good job! For the second part (where dp is needed), all solutions use a very similar approach. For the first part, all 3 solutions (including mine) have a different approach. :) That's the beauty of string problems.

Last edit: 2020-06-19 06:37:49
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?

RE: Conjuctions and adpositions should only be considered when they occur separately. For e.g. for the case below you cannot ignore the word "fork" as it is not a conjuction or adposition. This means some prefix of this string "should" always be included in the acronym. However, if you have words like "for", "with" etc., then they can be skipped completely. Hope these samples will clarify the above cases:

1
2
fork
forks
fork

Answer = 0

1
2
fork
forks
for

Answer = 1

Does this mean that if there is a word called "fork", we can either choose to take "for" from it or ignore it completely as in sample 2? And both taking and skipping it are counted as different ways?

RE: Yes, taking it and skipping are 2 different ways. This should be clear in sample 2 (where "for" can be skipped, but "forest" cannot be).

Also what's the output for this one? 1 or 2?
1
2
aa
a
a

RE: The answer for this case is 1.

Last edit: 2020-06-10 12:29:38
[Rampage] Blue.Mary: 2020-06-08 03:25:11

After constraints change my program becomes very heavy & ugly...

RE: There is a less ugly solution for the preprocessing step with the same time complexity as yours, instead of using what you used. However, the less ugly solution is more memory intensive and has a higher constant factor. Your solution runs around 3x faster. Congrats! :D

Last edit: 2020-06-08 10:43:22
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