logo AlgoBeat OnlineJudge
登录 注册

#104340. [BZOJ 4340] BJOI2015 隐身术

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

题目描述

给定两个串A,B。请问B中有多少个非空子串和A的编辑距离不超过K?

所谓“子串”,指的是B中连续的一段。不同位置的内容相同的子串算作

多个。两个串之间的“编辑距离”指的是把一个串变成另一个串需要的最小的

操作次数,每次操作可以插入、删除或者替换一个字符。

输入格式

第一行一个非负整数K。接下来两行,每行一个由大写字母组成的字符

串,分别表示A和B。

输出格式

输出一行一个整数,表示所求答案。

样例

样例输入

1
AAA
AABBAAB

样例输出

5

数据范围与提示

对100%的数据,K≤5,两个字符串均非空,长度和小于10^5.