P1373. L-system

问题描述

一个 D0L（确定性无交互的 Lindenmayer 系统）由以下部分组成：

• 一个有限的符号集 SIGMA（称为字母表）。
• 一个有限的生成式集合 P。
• 一个起始字符串 w。

生成式 P 中的每个生成式形式为 x -> u，其中 x 是 SIGMA 中的一个符号，u 是 SIGMA+ 中的一个字符串（u 被称为生成式的右侧）。SIGMA+ 是所有由 SIGMA 中符号组成的非空字符串的集合。这样的生成式表示将符号 x 转换为字符串 u。对于 SIGMA 中的每个符号 x，P 中恰好包含一个形式为 x -> u 的生成式。

直接推导是指从字符串 u1 到 u2 的转换，即将 u1 中的每个 SIGMA 中的符号 x 替换为该符号生成式的右侧字符串。D0L 系统的语言由所有可以通过从起始字符串 w 经过一系列直接推导得到的字符串组成。

假设字母表由两个符号 a 和 b 组成。生成式集合包含两个生成式，形式为 a -> u 和 b -> v，其中 u 和 v 是 {a, b}+ 中的字符串，起始字符串 w 是 {a, b}+ 中的字符串。现在的问题是：给定一个字符串 z，是否存在 D0L 系统语言中形式为 xzy 的字符串（其中 x 和 y 是 SIGMA* 中的任意字符串，SIGMA* 是所有由 SIGMA 中符号组成的字符串的集合，包括空字符串）？当然可以。请编写一个程序来解决这个问题。

输入

程序的输入由若干块组成。每块包含四行。任意两个连续块之间没有空行。每块的第一行是符号 a 的生成式右侧，第二行是符号 b 的生成式右侧，第三行是起始字符串，第四行是给定的字符串 z。生成式右侧、起始字符串和给定的字符串 z 的长度均不超过 15 个字符。

输出

对于输入中的每个块，输出一行，内容为 YES 或 NO，表示是否存在符合问题描述的字符串。

输入示例 1

aa
bb
ab
aaabb
a
b
ab
ba

输出示例 1

YES
NO

来源

Central Europe 1996

如果需要进一步帮助，请告诉我！