CF271D Good Substrings

你有一个由小写英文字母组成的字符串 $s$。其中一些英文字母是“好”的，剩下的则是“坏”的。 字符串 $s$ 的一个子串 $s[l...r]$（$1 \leq l \leq r \leq |s|$），即 $s = s_1s_2...s_{|s|}$（其中 $|s|$ 表示字符串 $s$ 的长度），定义为 $s_l s_{l+1}...s_r$。 如果子串 $s[l...r]$ 中的字母 $s_l, s_{l+1}, ..., s_r$ 至多有 $k$ 个是“坏”的（具体见样例解释），我们称该子串为“好子串”。 你的任务是计算字符串 $s$ 中不同的好子串的数量。两个子串 $s[x...y]$ 和 $s[p...q]$ 被认为是不同的，当且仅当它们的内容不相同，即 $s[x...y] \neq s[p...q]$。

第一行输入一个非空字符串 $s$，由小写英文字母组成，长度不超过 $1500$。 第二行输入一个仅由字符“0”和“1”组成的字符串，长度恰为 $26$。如果这个字符串的第 $i$ 个字符为“1”，则第 $i$ 个英文字母是“好”的，否则是“坏”的。也就是说，这一行的第一个字符对应字母 $a$，第二个对应 $b$，以此类推。 第三行输入一个整数 $k$（$0 \le k \le |s|$），表示一个好子串中最多可以包含的“坏”字符数。

输出一个整数，表示字符串 $s$ 中不同的好子串的数量。

在第一个样例中，所有好子串有："a"、"ab"、"b"、"ba"、"bab"。 在第二个样例中，所有好子串有："a"、"aa"、"ac"、"b"、"ba"、"c"、"ca"、"cb"。 由 ChatGPT 5 翻译