题意

求满足\(\le n\)且不包含集合\(S\)中任意字符串作为子串的个数。

分析

多子串问题,考虑在AC自动机上dp。

\(f[i][j][k]\)表示到数字的第\(i\)位,对应AC自动机上的第\(j\)位,是否有最高位的限制\(k=0/1\)。

直接通过AC自动机getfail以后的\(ch\)数组转移即可。

有一类特殊情况是字符集\(S\)包含前导\(0\),而数字中的前导\(0\)会被去掉,又一个方便的处理办法是手动把AC自动机中的\(ch[0][0]\)边删除。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注