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