奶牛情书 (ac自动机+dp)

题意

• 一个奶牛知道一些单词，现在有一个长度n的文本，问你这个文本至少包含一个奶牛会的单词的方案数。

  分析

• 正向算至少包含一个太麻烦了，所以就逆向算，算出总的(快速幂取模)，再算出一个都不包含的情况。而怎么才能算出一个都不包含的情况呢。这个就涉及了自动机套dp。

• 方案数用到dp这个都能够想到，可是字符串如何用状态表示呢。这个就要用到前缀了，把每一个前缀看做一个状态，那么添加一个字符之后所形成的前缀成为了另外一种状态（这里需要注意的是空串也是一种特殊的前缀）。

• 但是怎么很快得到所有的前缀并能得到他们的转移方向呢，很简单，那就是ac自动机。他把每一个字符串的前缀都体现出来了，ac自动机的节点数就是这里的状态数，ac自动机另外也可以叫做有限状态机，状态就这样来了

2.

• 在禁止一些字符串时，少考虑了把包含这个字符串的其他前缀串都禁止了。比如aba和ccabac，我们现在要把这两个串禁止用，但是单禁止这两个串还不行，因为我们的一个前缀状态是ccaba,ccaba就包含了禁止串，所以我们要这样禁止一个串：如果他的失配后指向的串被禁止了那么当前的串也要禁止。 if(cnt[fail[u]]) cnt[u] = 1;

思考

1. 只要懂了原理就很简单了，没有坑点

2. 这个类型的ac自动机加dp帮我更好理解自动机。之前对于ac自动机的根节点和fail数组并不是很理解，现在想就是root节点就是空节点。fail指针就相当于在这个节点添加一个字符匹配失配后我还能够匹配哪里。