题意

求包含集合\(S\)中任意个字符串为子串,且长度为\(m\)的字符串个数。

分析

考虑在AC自动机上dp。

用\(f[i][j][k]\)表示到字符串的第\(i\)位,对应AC自动机上的结点\(j\),是否已经包含了至少一个作为子串\(k=0/1\)。

显然如果当前结点为一个字符串的结尾,或者当前结点的 fail 链上有单词的结尾,当前的位置就是集合中某一个字符串的结尾。

 


发表评论

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