luogu#P2138. 小Z的关系距离

小Z的关系距离

题目描述

小 Z 学习了辩证唯物主义,知道了联系具有普遍性。他看着草稿纸上的字符串,就想挖掘它们之间的关系。

小 Z 认为,对于两个字符串 a,ba,b,如果它们各自删除不超过其自身长度一半的字符能够相等,则称 a,ba,b 有距离为 11 的关系。而如果存在另一个字符串 cc,它和 aa 有距离为 11 的关系,和 bb 有距离为 nn 的关系,则称 a,ba,b 有距离为 n+1n + 1 的关系。

现在小 Z 随机挑选出了两个小写字母字符串 a,ba,b,想知道它们之间关系的最小距离,希望你帮帮他。

输入格式

第一行包含一个字符串 aa

第二行包含一个字符串 bb

输出格式

第一行包含一个整数,表示 a,ba,b 之间关系的最小距离。

abcdef
axcyd
1
a
b
2
abb
baa
2

提示

对于 30%30\% 的数据,a,ba,b 由同一字母构成。

对于 100%100\% 的数据,1a,b1001 \leq |a|,|b| \leq 100