ACMAKER - ACM (ACronymMaker)

The sadists who design problems for ACM programming contests often like to include the abbre- viation “ACM” somewhere in their problem descriptions. Thus, in years past, the World Finals has had problems involving “Apartment Construction Management,” the “Atheneum of Culture and Movies,” the “Association of Cover Manufacturers,” “ACM Airlines,” the “Association for Computa- tional Marinelife,” and even an insect named “Amelia Cheese Mite.” However, the number of word combinations beginning with A, C, and M that make sense is finite and the problem writers are starting to run out of ideas (it’s hard to think of problems about “Antidisestablishmentarianistic Chthonian Metalinguistics”). Fortunately, modern culture allows more flexibility in designing abbreviations — consider, for example:

GDB — Gnu DeBugger
LINUX — either “LINus’s UniX” or “LINUs’s miniX” or “Linux Is Not UniX”
SNOBOL — StriNg Oriented symBOlic Language
SPITBOL — SPeedy ImplemenTation of snoBOL

The rules used in these examples seem to be:

  • Insignificant words (such as “of”, “a”, “the”, etc.) are ignored.
  • The letters of the abbreviation must appear, in the correct order, as an ordered sublist of the letters in the significant words of the phrase to be abbreviated.
  • At least one letter of the abbreviation must come from every significant word (multiple occurrences of a letter are, of course, treated as distinct).

Of course these rules are often broken in real life. For instance, RADAR is an abbreviation for “RAdio Detecting And Ranging”. Under our rules (assuming that “and” is an insignificant word), this would not be a valid abbreviation (however, RADR or RADRAN or DODGING would be valid). You have been asked to take a list of insignificant words and a list of abbreviations and phrases and to determine in how many ways each abbreviation can be formed from the corresponding phrase according to the rules above.

Input

The input file consists of multiple scenarios. Each scenario begins with an integer 100 >= n >= 1 followed by n insignificant words, all in lower case, one per line with no extra white space. (A line containing 0 indicates end of input.) Following this are one or more test cases for this scenario, one per line, followed by a line containing the phrase “LAST CASE”. Each line containing a test case begins with an abbreviation (uppercase letters only) followed by a phrase (lowercase letters and spaces only). The abbreviation has length at least 1 and the phrase contains at least one significant word. No input line (including abbreviation, phrase, and spaces) will contain more than 150 characters. Within these limits, however, abbreviations and phrase words may be any length.

Output

For each test case, output the abbreviation followed by either

is not a valid abbreviation

or

can be formed in i ways

where i is the number of different ways in which the letters of the abbreviation may be assigned to the letters in the phrase according to the rules above. The value of i will not exceed the range of a 32-bit signed integer.

Example

Input:
2
and
of
ACM academy of computer makers
RADAR radio detection and ranging
LAST CASE
2
a
an
APPLY an apple a day
LAST CASE
0

Output:
ACM can be formed in 2 ways
RADAR is not a valid abbreviation
APPLY can be formed in 1 ways

Added by:Camilo Andrés Varela León
Date:2007-07-26
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:East Central North America 2005

hide comments
2022-10-28 10:27:45
can someone provide me accepted solution in Java for this problem? I tried both top-down and bottom-up but it didn't work out in Java and everytime it gave TLE but it got AC in c++.
2022-10-09 08:24:25
made me realise to consider whether the thought state is unique or not. Very good problem
2021-10-04 04:54:47 Tomasz Rzepecki
I wish PyPy 3 was supported. It's a bit annoying having to port everything back to Python 2 just to get PyPy to work, and for a lot of problems cPython doesn't cut it, unfortunately.
2021-05-06 12:01:18
Think locally about each word.....and how it would carry forward the acronym.....nice dp.
2020-08-07 17:06:03
As others have pointed out , be careful -
1. With lowercase conversions.
2. While skipping input based on insignificant words.
3. Extra spaces between words and at end.

Last edit: 2020-08-07 17:06:42
2020-07-23 19:08:46
Be careful while converting string to lowerCase
2020-06-29 21:45:05 Shubham Jadhav
nice dp
2020-06-03 08:11:12
@nashugame remove all the insignificant words from the string then compute for ex in first example remove of from ACM string and remove and from RADAR string
2020-06-01 07:36:48
Can someone provide test cases?
2020-05-20 14:59:41
Which are the words to actually remove?
Do we have to remove the words which are mentioned already or more, because there are many such words.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.