【JSOI2007】文本生成器


题意

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

分析

考虑在AC自动机上dp。

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

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

 

You may also like

【TJOI2015】弦论

【AHOI2013】差异

LEAVE A COMMENT

Statistics

  • 0
  • 8,090

Categories

Archive

Comments