UOJ Logo

NOI.AC

1S 512MB

#1595. 字符串大师

Statistics

题目描述

所谓最长公共子串,比如串 A: “abcde”,串 B: “jcdkl”,则它们的最长公共子串为串 “cd”,即长度最长的字符串,且在两个串中都作为连续子串出现过。 给定两个长度都为 $n$ 的字符串,对于字符串大师的你来说,求它们的最长公共子串再简单不过了。 所以现在你有 $k$ 次修改机会,每次你可以选择其中某个串的某个位置,将其修改成任意字符。 你需要合理使用这 $k$ 次修改机会,使得修改之后两个串的最长公共子串最长。相信对于字符串大师的你来说,这个问题也难不倒你。

输入格式

第一行包含两个整数 $n,k$,分别表示字符串的长度和修改次数。 第二行包含一个长度为 $n$ 的仅由小写字符构成的字符串 $S$。 第三行包含一个长度为 $n$ 的仅由小写字符构成的字符串 $T$。

输出格式

输出一行一个整数,即修改完毕之后两个串的最长公共子串的长度。

输入样例1

5 0
abcde
jcdkl

输出样例1

2

输入样例2

5 2
aaaaa
ababa

输出样例2

5

数据范围

对于 $100\%$ 的数据, $0 \leq k \leq n$。 对于$20\%$的数据$1 \leq n \leq 10 , k = 0 $ 对于$50\%$的数据$1 \leq n \leq 10 ,k = 1$ 对于$100\%$的数据$1 \leq n \leq 300 , 0 \leq k \leq 300$