有一个只包含小写字母,长度为 n 的字符串 S 。有一些字母是好的,剩下的是坏的。
定义一个子串 S_{l\ldots r} 是好的,当且仅当这个子串包含不超过 k 个坏的字母。
求有多少个不同的满足以下要求的字符串 T :
第一行有一个字符串 S 。
第二行有一个字符串 B 。若 B_i= '1' 则表示 S_i 是好的,否则表示 S_i 是坏的。
'1'
第三行有一个整数 k 。
一个整数:答案。
ababab 010101 1
5
所有'b'是好的,'a'是坏的。
'b'
'a'
满足条件的字符串有:"a","ab","b","ba","bab"。
"a"
"ab"
"b"
"ba"
"bab"
ababab 100000 1
3
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