BZOJ 4502 串 题解

妙妙数数题

key：数数题通常是，对于特定形式的计数，就盯着这个模式观察，看出一些充要条件、计数形式的转化，然后想办法维护。

优化的本质就是把难算的变成好算的，把不好一起统计的（只能一个个数的）以某种角度、用某些数据结构，一起统计（多个多个数）。

我觉得难点通常在于“盯出一些充要条件”，这也是他的主要思维难度所在

如何“盯着这个模式观察”？就像解不等式一样，先不要急着去数他，先列出一个个条件，把限制条件进行充分的理解、充分的转化，再想办法维护他。

Statement

Solution

用总方案数减去重复的方案数，总方案数显然是 trie 树点数的平方。

对于两个重复的方案 \(A+B=C+D\)，其中 \(|A|<|C|\)

\(D\) 是 \(B\) 的后缀

\(A\) 是 \(C\) 的前缀，即只要存在 \(C\) 就一定存在 \(A\)，所以固定 \(B,D\) 算 \(C\) 的数量

设 \(E+D=B\)，有 \(C\) 是 \(E\) 的后缀，这就成了一个数 \(C\) 的充要条件

即 \(C\) 的数量为 \(E\) 的 fail 树子树大小

再要求一个“\(D\) 是 \(B\) 的最长的出现过的后缀”就完美了，也就是 \(D\) 是 \(B\) 的 fail 指针指向的串

对上面这段不懂的强烈建议一句一句看，并画个图理解。

于是方法就出来了：在 AC 自动机上枚举 \(B\) 点，令 \(\text{fail}(B)=D\)，设 \(B,D\) 右对齐后相差的串为 \(E\)，每次答案加上 \(E\) 的 fail 树子树大小减一。

这样的 \(\sum|E|\) 是 trie 树大小级别的。

会不会算重、算漏？不会，想要证明的留作习题。

通过这几道题，我们得到启示：AC 自动机既可以处理“前缀”关系也可以处理“后缀”关系，前缀关系通过 trie 来维护，后缀关系通过 fail 树来维护；前后缀关系可以通过 把串反过来 互相转化。