#3326. 「SNOI2020」字符串

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

有两个长度为 n 的由小写字母组成的字符串 a,b ,取出他们所有长为 k 的子串(各有 n-k+1 个),这些子串分别组成集合 A,B 。现在要修改 A 中的串,使得 A B 完全相同。可以任意次选择修改 A 中一个串的一段后缀,花费为这段后缀的长度。总花费为每次修改花费之和,求总花费的最小值。

输入格式

第一行两个整数 n,k 表示字符串长度和子串长度;

第二行一个小写字母字符串 a

第三行一个小写字母字符串 b

输出格式

输出一行一个整数表示总花费的最小值。

样例

样例输入

5 3
aabaa
ababa

样例输出

3

样例解释

所有子串为: A = \{aab,aba,baa\}, B = \{aba, bab, aba\} 。可以看出有一对 aba 是相同的,另外要把 aab 改成 aba (花费 2 ), baa 改成 bab (花费 1 ),总花费为 3

数据范围与提示

对于所有数据, 1\le k\le n\le 1.5\times 10^5

  • 对于 10\% 的数据, n\le 11
  • 对于另外 20\% 的数据, n\le 200
  • 对于另外 20\% 的数据, n\le 2000
  • 对于另外 10\% 的数据,字符串的每一位在小写字母中均匀随机;
  • 对于余下 40\% 的数据,无特殊限制。