#1733. [NOIP2002 提高组] 字串变换

[NOIP2002 提高组] 字串变换

题目背景

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

题目描述

已知有两个字串 A,BA,B 及一组字串变换的规则(至多 66 个规则):

A1B1A_1\to B_1

A2B2A_2\to B_2

规则的含义为:在 AA 中的子串 A1A_1 可以变换为 B1 B_1A2A_2 可以变换为 B2B_2\cdots

例如:A=abcdA=\text{abcd}B=xyzB=\text{xyz}

变换规则为:

abcxu\text{abc}\rightarrow\text{xu}udy\text{ud}\rightarrow\text{y}yyz\text{y}\rightarrow\text{yz}

则此时,AA 可以经过一系列的变换变为 BB,其变换的过程为:

abcdxudxyxyz\text{abcd}\rightarrow\text{xud}\rightarrow\text{xy}\rightarrow\text{xyz}

共进行了 33 次变换,使得 AA 变换为 BB

输入格式

输入格式如下:

AA BB
A1A_1 B1B_1
A2A_2 B2B_2 |-> 变换规则

... .../

所有字符串长度的上限为 2020

输出格式

若在 1010 步(包含 1010 步)以内能将 AA 变换为 BB,则输出最少的变换步数;否则输出 NO ANSWER!

样例 #1

样例输入 #1

abcd xyz
abc xu
ud y
y yz

样例输出 #1

3

提示

【题目来源】

NOIP 2002 提高组第二题