#3817. 练8-神秘古卷的变换试炼
练8-神秘古卷的变换试炼
🏫 兔猫信奥学院:神秘古卷的变换试炼
在兔猫信奥学院的古籍库中,加菲老师将两张神秘古卷交给了小兔和小猫。这两张古卷分别记载着咒语 和咒语 。据说,如果能把咒语 中的一段文字,按照规定的代价转换成古卷 中对应位置的文字,就能解开隐藏已久的秘密。
转化过程中,第 个字符从 变为 所需的能量耗费为 (即两个字符的 ASCII 码差的绝对值)。古籍库规定,进行转换的总能量消耗不能超过预算 。如果你能将 的某个子串完全转变成 中对应位置的子串,而总消耗不超过预算,则该子串视为“成功转化”。
小兔和小猫决定全力以赴,以期获得破解古卷秘密的钥匙。请你帮助他们编写程序,求出可以成功转化的子串中最大的长度。
💡【题目描述】
给定两个长度相同的字符串 和 ,以及一个预算 。将 中第 个字符变为 中第 个字符需要消耗 的能量。如果你可以将 的某个子串转化为 中对应的子串,且总能量消耗不超过 ,则返回可以转化的子串的最大长度;否则返回 。
📥【输入格式】
- 第一行包含两个正整数 和 ,其中 表示字符串的长度。
- 第二行包含长度为 的字符串 (仅包含小写字母)。
- 第三行包含长度为 的字符串 (仅包含小写字母)。
📤【输出格式】
- 输出一个整数,表示可以成功转化的子串的最大长度。
📌【数据范围】
- 和 均只包含小写英文字母
💡【输入输出样例】
样例输入 1
4 3
abcd
bcdf
样例输出 1
3
解释:将 中的 "abc" 转换为 中的 "bcd",总能量消耗为 ,在预算之内,所以最大转换子串长度为 3。
样例输入 2
4 3
abcd
cdef
样例输出 2
1
解释:任一字符转换的能量消耗均为 2,无法转换超过 1 个字符的子串。
样例输入 3
4 0
abcd
acde
样例输出 3
1
解释:只有不转换时才能成功,因此最大转换子串长度为 1。