A116.字串变换

提高+/省选-

NOIP提高组

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

  • A1B1A_1\to B_1
  • A2B2A_2\to B_2

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

例如:A=abcdA=\texttt{abcd}BxyzB=\texttt{xyz}

变换规则为:

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

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

  • abcdxudxyxyz\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}

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

输入格式

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

接下来若干行,每行有两个字符串 Ai,BiA_i,B_i,表示一条变换规则。

输出格式

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

输入输出样例

  • 输入#1

    abcd xyz
    abc xu
    ud y
    y yz

    输出#1

    3

说明/提示

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

首页