题解 P4052 【[JSOI2007]文本生成器】
第一次做在AC自动机上跑DP的题……
之前做的好像都是乱搞
学长说AC自动机的DP都非常套路
大部分f[i][j]表示当前在节点j,且串长为i时的情况，
有时再加一维表示这个状态里面包含了哪些东西
而且AC自动机的DP会经常让你用矩阵乘法优化
那么对于这个题，我们可以先将AC自动机建立出来，然后搞一个简单的容斥
用所有的情况减去不可读的情况。
那么那些是不可读的情况呢？当然就是跑不到单词结尾节点的情况喽……
定义f[i][j]表示当前在j点且串长为i时不经过单词结尾的路径条数
然后从父亲往儿子转移即可
注意如果一个单词的后缀是一个可读单词(即fail指针指向可读单词的结尾节点)
那么这个单词一定也是可读的，我们就不能往这个单词走了
话说之前我好像做过类似的不过没有吸取教训QvQ活该WA好久
代码