#P4340. BJOI2015 隐身术

    ID: 3547 传统题 1000ms 512MiB 尝试: 190 已通过: 54 难度: 8 上传者: 标签>CF2500提高+/省选-深度优先搜索后缀数组Kasai 算法LCP+RMQST 表差分标记区间修改

BJOI2015 隐身术

[BJOI2015] 隐身术

题目描述

给定两个串AA、BB。请问 B ~B~中有多少个非空子串和 A ~A~的编辑距离不超过KK?

所谓“子串”,指的是 B ~B~中连续的一段。不同位置的内容相同的子串算作多个。两个串之间的“编辑距离”指的是把一个串变成另一个串需要的最小的操作次数,每次操作可以插入、删除或者替换一个字符。

输入格式

第一行一个非负整数KK。接下来两行,每行一个由大写字母组成的字符 串,分别表示 A ~A~和 B ~B~。

输出格式

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

样例 #1

样例输入 #1

1
AAA
AABBAAB

样例输出 #1

5

提示

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