[NOIP2002 提高组] 字串变换

字串变换"/>

[NOIP2002 提高组] 字串变换

题目背景

本题疑似错题，不保证存在靠谱的多项式复杂度的做法。测试数据非常的水，各种做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。

题目描述

已知有两个字串 A , B A,B A,B 及一组字串变换的规则（至多 6 6 6 个规则），形如：

• A 1 → B 1 A_1\to B_1 A1​→B1​。
• A 2 → B 2 A_2\to B_2 A2​→B2​。

规则的含义为：在 A A A 中的子串 A 1 A_1 A1​ 可以变换为 $ B_1 ， ， ，A_2$ 可以变换为 B 2 ⋯ B_2\cdots B2​⋯。

例如： A = abcd A=\texttt{abcd} A=abcd， B ＝ xyz B＝\texttt{xyz} B＝xyz，

变换规则为：

• abc → xu \texttt{abc}\rightarrow\texttt{xu} abc→xu， ud → y \texttt{ud}\rightarrow\texttt{y} ud→y， y → yz \texttt{y}\rightarrow\texttt{yz} y→yz。

则此时， A A A 可以经过一系列的变换变为 B B B，其变换的过程为：

• abcd → xud → xy → xyz \texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz} abcd→xud→xy→xyz。

共进行了 3 3 3 次变换，使得 A A A 变换为 B B B。

输入格式

第一行有两个字符串 A , B A,B A,B。

接下来若干行，每行有两个字符串 A i , B i A_i,B_i Ai​,Bi​，表示一条变换规则。

输出格式

若在 10 10 10 步（包含 10 10 10 步）以内能将 A A A 变换为 B B B，则输出最少的变换步数；否则输出 NO ANSWER!。

样例 #1

样例输入 #1

abcd xyz
abc xu
ud y
y yz

样例输出 #1

3

提示

对于 100 % 100\% 100% 数据，保证所有字符串长度的上限为 20 20 20。

【题目来源】

NOIP 2002 提高组第二题