题解 P4052 【[JSOI2007]文本生成器】

问题一 假设只有一个单词，怎么做？

对单词左个KMP, 设F[i,j]为已构成长度为i,单词匹配到位置j的,且没有一次匹配完全的方案数.显然,转移方程是:

最终答案为26^m-F[m,*].(很显然的补集转化)

问题二 现在有很多个单词, 怎么做?

多个单词的做法, 把单词们做成Trie图, 方程也就变成:

(j此时代表 Trie图 上的一个节点, 匹配完全指的就是经过带有end标记的节点.)

诶,不跳FAIL链啦? 笨,Tire图已经把这个过程优化掉了了.在标准的ACAM里,如果当前节点存在儿子c,直接转移过去; 不然,就得条FAIL链.但是,咱不是有这样一句话吗?

at void build():
    if(!Trie[x].ch[i]) Trie[x].ch[i]=Tire[Trie[x].fail].ch[i];

巧妙吧?

注意 若一个点的 FAIL链 里存在某个单词的 end标记 ,显然这个点是GG的. (这个点代表一个字串, FAIL链 上的点代表的字串这个字串的后缀) 这个性质太有用了.

代码补贴了.