A6017 | $「2017 山东三轮集训 Day5」Fantasy$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

JOHNKRAM 收到了一个字符串 $ S $，但他不喜欢这个串，他决定把它变成 $ T $。 JOHNKRAM 最近学习了一些后缀数据结构，他相信通过替换后缀可以实现一切操作。他有 $ m $ 种替换方式，每种替换方式包含两个等长的字符串 $ u $ 和 $ v $，如果当前 $ u $ 是 $ S $ 的后缀，则可以将 $ S $ 的后缀 $ u $ 替换成 $ v $。 现在 JOHNKRAM 希望你能帮他计算出，最少需要替换多少次才能将 $ S $ 变成 $ T $。

一个测试点包含多组数据。 每组数据第一行包含两个字符串 $ S $ 和 $ T $ 以及一个整数 $ n $，意思如题所示。 接下来 $ n $ 行每行两个字符串 $ u $ 和 $ v $，表示一种替换方式。 输入文件以一个 . 结束。

对于每一组数据，输出该组数据编号以及最小步数，如果无解输出 No Solution 。格式参见样例。

输入 #1

AA BB 4
A B
AB BA
AA CC
CC BB
A B 3
A C
B C
c B
.

输出 #1

Case 1: 2
Case 2: No solution

C++ 编辑器

输入

输出