#BZOJ1030

BZOJ1030 [JSOI2007]文本生成器 AC自动机 动态规划

   给出n个模式串,问长度为m的串中有多少个至少含有这n个模式串中的任意一个。  注意,所有的串仅由A~Z26个大写字母构成。   AC自动机好题。  先构建一个AC自动机。  然后在AC自动机上面跑dp。  建议开滚动数组。  dp[i][j]表示长度为i,在AC自动机上面走到了j的方案数。  ...