#PQJ319x6228. QOJ 319_6228

    ID: 2913 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2020字符串

QOJ 319_6228

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

输入格式

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

第二行一个小写字母字符串 aa;

第三行一个小写字母字符串 bb。

输出格式

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

样例数据

样例输入

5 3 aabaa ababa

样例输出

3

样例解释

所有子串为:A={aab,aba,baa},B={aba,bab,aba}A = \{aab,aba,baa\}, B = \{aba, bab, aba\}。可以看出有一对 abaaba 是相同的,另外要把 aabaab 改成 abaaba(花费 22),baabaa 改成 babbab(花费 11),总花费为 33。

子任务

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

对于 10%10\% 的数据,n≤11n\le 11;

对于另外 20%20\% 的数据,n≤200n\le 200;

对于另外 20%20\% 的数据,n≤2000n\le 2000;

对于另外 10%10\% 的数据,字符串的每一位在小写字母中均匀随机;

对于余下 40%40\% 的数据,无特殊限制。