P1624 Word Abbreviation

Shushu noticed that many computer terms are abbreviations. For example, GDB is the abbreviation of Gnu DeBug. However, sometimes an abbreviation may have multiple possible full forms. For example, LINUX can be understood as: 1. LINus’s UniX 2. LINUs’s miniX 3. Linux Is Not UniX Now Shushu gives an abbreviation and a fixed full form (several words separated by spaces). Some words in the full form may be invalid and should be ignored. A valid abbreviation requires that: - Each valid word contributes at least one character that appears in the abbreviation. - The selected letters must appear in order in the full form (within each word and across words). For the given abbreviation and full form, how many interpretations are there? An interpretation is defined by the positions of the letters chosen in each valid word. If any letter’s position differs, they are considered different interpretations.

The first line contains an integer $N$, the number of invalid words. The next $N$ lines each contain one invalid word, consisting of lowercase letters. Then follow multiple queries. Each query provides an abbreviation (uppercase letters only) followed by a full form. Input ends with a line containing `LASTCASE`.

For each query, first output the abbreviation. If the abbreviation is not valid, output `is not a valid abbreviation`; otherwise, output `can be formed in i ways` (where $i$ is the number of interpretations).

Constraints For all testdata, $1 \le N \le 100$, the length of each string does not exceed $150$, the number of queries does not exceed $20$, and the number of interpretations does not exceed $10^9$. Translated by ChatGPT 5