Word equations

You are given a text $T$ and a pattern $P$. You want to check if you can erase some of the letters of $T$ so that the remaining symbols produce exactly $P$. For example, the word programming can be partially erased to obtain pong or program or roaming (but not map, as the letters must remain in the same order). Both words consist of small letters of the English alphabet only.

There is just one catch: the text $T$ is encoded by a system of equations. The equations use special symbols (every symbol is denoted by a word in capital letters), each of them encoding some word over the alphabet {a,...,z}. Each equation is of one of the following forms:

A = a word over {a,...,z}

or

A = B + C

where A, B, C can be any special symbols, and the + sign denotes the concatenation of words. The system is:

• unambiguous - for a fixed symbol A, there is exactly one equation with A on the left-hand side, and

• acyclic - if you start from any symbol A and make substitutions according to the equations (right-hand side for left-hand side), you can never obtain an expression containing A again.

Such a system always has a unique solution. For example, in the system:

• START = FIRST + SECND

• FIRST = D + E

• SECND = F + E

• D = good

• E = times

• F = bad

the symbol START encodes the word goodtimesbadtimes.

Given a single word $P$ as the pattern, a system of equations, and one particular starting symbol $S$ of this system, determine whether the pattern $P$ is present in the word encoded by $S$.