L-system Substring

A D0L system (a deterministic Lindenmayer system without interaction) consists of a finite alphabet $\Sigma$, a finite set of productions $P$, and a starting string $w$. Every production has the form $x \to u$, where $x \in \Sigma$ and $u \in \Sigma^{+}$ (a nonempty string over $\Sigma$); for each symbol $x \in \Sigma$ the set $P$ contains exactly one production whose left side is $x$.

A direct derivation turns one string into another by simultaneously replacing every symbol of the string with the right side of its production. The language of the system is the set of all strings that can be obtained from $w$ by applying zero or more direct derivations (so $w$ itself belongs to the language).

Here the alphabet is $\Sigma = \{a, b\}$, so there are exactly two productions, $a \to u$ and $b \to v$ with $u, v \in \{a, b\}^{+}$, and the starting string is $w \in \{a, b\}^{+}$.

Given a string $z$, decide whether the language contains at least one string of the form $x\,z\,y$ with $x, y \in \{a, b\}^{*}$ — equivalently, whether $z$ occurs as a contiguous substring of some string in the language.

The input contains several blocks and ends at end of file; there are no blank lines between consecutive blocks. Each block consists of exactly four lines:

1. the right side $u$ of the production $a \to u$;
2. the right side $v$ of the production $b \to v$;
3. the starting string $w$;
4. the query string $z$.

Each of these four strings is nonempty, consists only of the letters $a$ and $b$, and has length at most $15$.

For each block, print a single line containing YES if some string in the language contains $z$ as a substring, and NO otherwise.