1300: E-解救艾希
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:6
Solved:1
Description
在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄进入中毒状态。
不巧的是,在一次战斗中,弗雷尔卓德的英雄艾希被提莫的飞箭命中导致中毒,为了解救艾希,泰达米尔决定偷袭提莫的营地获取解药。不巧的是,即使突袭非常顺利,提莫还是隐身逃跑了,但是装有解药的箱子被泰达米尔抢了过来。
这个箱子是一个特制的密码箱,需要正确回答箱子上的问题才能成功打开箱子拿到解药。
箱子的问题如下:
现在给定2个字符串A与B,A和B都是由小写字母和问号组成的,问号可以变成任意字符(注意:‘ ? ’ 为英文字符!!!!!)。
请你找出最短的字符串S,要求S包含A和B两个字符串,只需要计算出所有符合要求的长度最短的S的长度L即可打开箱子。
这下泰达米尔傻眼了,于是只好求助你来解决这个问题,你能够解决这个问题成功解救艾希吗?
Input
A,∣A∣≤6000。第二行一个字符串B, ∣B∣≤6000。(|A|代表字符串A
Output
S的长度L
Sample Input Copy
abcd
?de
Sample Output Copy
5
HINT
样例解释:
最短的S为“abcde”,其中包含了“abcd”和“?de”,其中'?'变成‘c’
子串解释:
串中任意个连续的字符组成的子序列称为该串的子串
如“abc”是“abcde”的子串,但不是“adbc”的子串