← 返回题目列表

Codeforces · 271/D

D. 好的子串

中文机器翻译题面 查看原题

你有字符串 s,由小英文字母组成。有些英文字母很好,其余的很糟糕。

字符串 s = s1s2...s|s| 的子串 s[l...r] (1 ≤ l ≤ r ≤ |s|) (其中 |s| 是字符串 s 的长度)是字符串 slsl + 1...sr。

子串 s[l...r] 是好的,如果字母 sl, sl + 1, ..., sr 中最多有 k 个坏的(看示例的解释可以更清楚地理解)。

你的任务是找到给定字符串 s 的不同好子串的数量。如果两个子字符串 s[x...y] 和 s[p...q] 的内容不同,则认为它们是不同的,即 s[x...y] ≠ s[p...q]。

输入

输入的第一行是非空字符串s,由小英文字母组成,字符串长度最多1500个字符。

第二行输入的是字符串“0”和“1”,长度正好是26个字符。如果这个字符串的第i个字符等于“1”,那么第i个英文字母就是好的,否则就是坏的。也就是说,该字符串的第一个字符对应于字母“a”,第二个字符对应于字母“b”,依此类推。

输入的第三行包含一个整数 k (0 ≤ k ≤ |s|) — 好子串中可接受的最大坏字符数。

输出

打印单个整数 — 字符串 s 的不同好子串的数量。

示例

输入 #1

ababab
01000000000000000000000000
1

输出 #1

5

输入 #2

acbacbacaa
00000000000000000000000000
2

输出 #2

8

注意

在第一个示例中,有以下好的子字符串:“a”、“ab”、“b”、“ba”、“bab”。

在第二个示例中,有以下好的子字符串:“a”、“aa”、“ac”、“b”、“ba”、“c”、“ca”、“cb”。