#P2138. 小Z的关系距离
小Z的关系距离
题目描述
小Z学习了辩证唯物主义,知道了联系具有普遍性。他看着草稿纸上的字符串,就想挖掘它们之间的关系。
小Z认为,对于两个字符串 a、b,如果它们各自删除不超过其自身长度一半的字符能够相等,则称a、b 有距离为 1 的关系。而如果存在另一个字符串 c,它和 a 有距离为 1 的关系,和 b 有距离为 n 的关系,则称 a、b 有距离为 n + 1 的关系。
现在小Z随机挑选出了两个小写字母字符串 a、b,想知道它们之间关系的最小距离,希望你帮帮他。
输入格式
第一行包含一个字符串 a。
第二行包含一个字符串 b。
输出格式
第一行包含一个整数,表示 a、b 之间关系的最小距离。
abcdef
axcyd
1
a
b
2
abb
baa
2
提示
【数据规模】
对于 30% 的数据,a、b 由同一字母构成。
对于 100% 的数据,1≤|a|,|b|≤100。