#6401. yww 与字符串

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

题目描述

有一个只包含小写字母,长度为 n 的字符串 S 。有一些字母是好的,剩下的是坏的。

定义一个子串 S_{l\ldots r} 是好的,当且仅当这个子串包含不超过 k 个坏的字母。

求有多少个不同的满足以下要求的字符串 T

  • T 作为 S 的子串出现过。
  • 存在一个 T 出现的位置 [l,r] ,满足 S_{l\ldots r} 是好的。

输入格式

第一行有一个字符串 S

第二行有一个字符串 B 。若 B_i= '1' 则表示 S_i 是好的,否则表示 S_i 是坏的。

第三行有一个整数 k

输出格式

一个整数:答案。

样例

样例一

input

ababab
010101
1

output

5

explanation

所有'b'是好的,'a'是坏的。

满足条件的字符串有:"a","ab","b","ba","bab"

样例二

input

ababab
100000
1

output

3

explanation

S_1 是好的,其他的字符都是坏的。

满足条件的字符串有:"a","ab","b"

虽然 S_{3\ldots4}=S_{5\ldots6}= "ab" 是坏的,但是这并不影响 "ab" 满足条件,因为 S_{1\ldots2}= "ab" 是好的。

数据范围与提示

子任务 1 10 分): n\leq 10

子任务 2 10 分): n\leq 100

子任务 3 10 分): n\leq 1000

子任务 4 10 分): n\leq 100000,k=n

子任务 5 10 分): n\leq 100000,k=0

子任务 6 20 分): n\leq 100000 ,若 S_i=S_j ,则 B_i=B_j

子任务 7 30 分): n\leq 100000

对于 100\% 的数据: 1\leq n\leq {10}^5,0\leq k\leq {10}^5 S 只包含小写字母。

题目来源:全是水题的GDOI模拟赛 by yww