QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[0]

# 6228. 字符串

Statistics

有两个长度为 n 的由小写字母组成的字符串 a,b,取出他们所有长为 k 的子串(各有 nk+1 个),这些子串分别组成集合 A,B。现在要修改 A 中的串,使得 AB 完全相同。可以任意次选择修改 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

子任务

对于所有数据,1kn1.5×105

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