#P2133. 天作之合
天作之合
题目背景
生活就是一次A*,你是我的第一个目标状态。——小明
题目描述
在小明的学校中,一共有若干个女生。小明认为每个女生的特征可以抽象为一个6位的数字串其中不重复地包含1~6这6个数码。
在小明心中,有一个理想的女生,她的特征数字串为A。如果串Y是串X交换两个连续的数码所得,那么我们认为特征数字串X和Y相似。首先,小明找到了他的同桌,她的特征数字串为S。每次,小明会寻找一个特征数字串和当前串相似的女生,直到寻找到适合他的(即特征数字串和A相同或相似的)。定义每个女生的合适程度为找到此人至少需要找女生的数量(包括他的同桌和此人自己)。显然,合适程度数值越小的女生越适合小明。
然而,小明觉得老天不会轻易地让他找到,所以他认为合适程度第二小的才是他最合适的伴侣(也就是小红)。那么,请你帮他写一个程序,求出对于小明,小红的合适程度是多少。
输入格式
第1行,一个特征数字串A。
第2行,一个特征数字串S。
输出格式
一行,一个正整数表示小红的合适程度。
123654
123456
3
提示
对于全部数据,保证串A和S合法,且保证能找到。
数据比较弱。