[BJOI2015] 隐身术
题目描述
给定两个串$A$、$B$。请问$~B~$中有多少个非空子串和$~A~$的编辑距离不超过$K$?
所谓“子串”,指的是$~B~$中连续的一段。不同位置的内容相同的子串算作多个。两个串之间的“编辑距离”指的是把一个串变成另一个串需要的最小的操作次数,每次操作可以插入、删除或者替换一个字符。
输入输出格式
输入格式
第一行一个非负整数$K$。接下来两行,每行一个由大写字母组成的字符
串,分别表示$~A~$和$~B~$。
输出格式
输出一行一个整数,表示所求答案。
输入输出样例
输入样例 #1
1
AAA
AABBAAB
输出样例 #1
5
说明
对$100\%$的数据,$K\leq5$,两个字符串均非空,长度和小于$10^5$。