字符串的期望本质不同子串个数
本篇文章研究了随机字符串期望的本质不同子串个数及其相关的性质。
本文中，一个字符串的本质不同子串被定义为其 非空的 不同子串个数。举例来说，abb 的本质不同子串有：a、b、ab、bb 和 abb。我们有一个问题：长度为 $n$、字符集大小为 $m$ 的随机字符串的期望本质不同子串个数是多少？
令所有长度为 $n$、字符集大小为 $m$ 的字符串构成的集合为 $S_{n,m}$。对于这个问题，我们可以简单将其转化为对所有 $S$ 中的字符串的本质不同子串个数求和。反向考虑，我们来枚举每种可能的子串 $s$ 并计算它被 $S$ 中多少种字符串包含。但是枚举这小的子串时间复杂度也是不优的，不过我们考虑到对于一些子串，包含它们的指定字符串数量是相同的。
更具体地，如果 $w$ 是一个字符串，我们令 $c_w(x)$ 为关于 $x$ 的一个函数，它的第 $i$ 项为系数为 1 当且仅当 $w$ 有一个长度为 $i$ 的周期（我们规定所有字符串都有一个长度为 0 的周期）；否则这一项系数为 0。令 $e_{w,i}$ 为长度为 $i$，字符集为 $m$ 的包含 $w$ 的字符串数量，然后另 $E_w(x)$ 为它关于 $i$ 的普通生成函数。有一个结论：
$$
E_w(x)=\frac{x^{|w|}}{(1-mx)(x^{|w|}+(1-mx)c_w(x))}
$$
这个的证明可以参看 这里。
假设我们已经得到了所有的 $c_w(x)$（后面会阐释本质不同的 $c_w©$ 并不多），然后算出 $E_w(x)$ 再乘上有多少个字符串 $w$ 的 $c_w(x)$ 为当前枚举的这个东西，我们就可以算出最终的答案。也就是说，现在我们对于每一个 $i\in [0,L-1]$ 都知道一个字符串是否有长度为 $i$ 的周期，而我们要求出满足条件的长度为 $L$ 的字符串个数。我们用二进制数 $v$ 代表这个 $c_w(x)$（因为系数只有 0 和 1），然后记 $f_v$ 为上面那个我们要求的值。
考虑容斥。我们先不考虑 不能有长度为 x 的周期 这个条件，我们只考虑有指定的一些周期的字符串共有多少个，记为 $S_v$。这个可以用并查集简单地做到 $O(n^2)$。具体地说，如果我们用并查集得到了有这些周期的字符串被分割为了 $K$ 个字符必须相同的下标集合，我们就称其自由元数目为 $K$。实际上这个 $K$ 实际上可以在枚举 $c_w(x)$ 时动态计算，复杂度就是线性了。显然我们有 $S_v=m^K$。然后运用容斥定理，我们对于每一个 $v$，得到它的 $f_v$ 就应该是：
所以我们现在可以对于一对给定的 $(n,m)$ 求得答案了。
我们先观察一下上面那个生成函数。首先求逆可以被改写为无限求和的形式，然后我们注意到 $m$ 总是和 $x$ 同时出现且原式没有出现 $x$ 的负指数项，因此可以发现该多项式展开后所有项中 $x$ 的次数大于等于 $y$ 的次数。由此我们得出 $n$ 确定时，答案为关于 $m$ 的一个次数不超过 $n$ 的多项式 $F_n$。下面给出了 $n=1,2,3$ 时的多项式：
$$ \begin{aligned} F_1(x)&=x\\ F_2(x)&=-x+3x^3\\ F_3(x)&=-3x^2+6x^3 \end{aligned} $$这里 以系数由低到高的形式给出了 $n=0\dots60$ 时的多项式。我们观察到一下几点性质：
- $[x^0]F_n(x)=0$：这个很显然，如果你字符集大小为 $0$ 根本无法组成任何字符串。
- $[x^n]F_n(x)=\frac{n(n+1)}2$。这个是尚未证明的猜想。
然后我们讲一下如何枚举 $c_w(x)$ 并对于一个 $c_w(x)$ 计算出其自由元的数目。这里参考了 Guibas 和 Odlyzko 在 Periods in Strings 中提到的一个判定周期向量 $v$（一个二进制向量，$v_i=1$ 当且仅当 $i$ 是周期）是否合法的方法。原文中定义 $0$ 是任何字符串的周期，我们也使用这一定义。记 $\pi(v)=\min\left\{t|v_t=1\land t\ne0\right\}$（即 $v$ 中的最小非零周期），若这样的最小值不存在，我们令 $\pi(v)=+\infty$。我们如下递归地定义推断 $\Xi(v)$：
$\Xi(v)$ 为真，当且仅当 $v$ 为空集；或 $v_0=1$，且满足下面两种互不相交的条件之一：
-
$\pi(v)\le\left\lfloor\frac{|v|}2\right\rfloor$，且对于任意 $\pi(v)$ 的倍数 $k$（$k<|v|$）都有 $v_k=1$；
且，令 $r=\pi(v)(\left\lfloor\frac n{\pi(v)}\right\rfloor-1)$、$w=v_{r\dots(|v|-1)}$ 时，有 $\pi(w)\ge p$ 或 $\pi(w)>(n-r-\pi(v))+(\pi(v),\pi(w))$；
且 $\Xi(w)$ 为真。
-
$\pi(v)>\left\lfloor\frac{|v|}2\right\rfloor$，且 $\Xi(v_{r\dots(|v|-1)})$ 为真。
我们可以根据这个推断来枚举所有合法的周期向量。枚举长度为 $n$ 的周期向量过程中，我们在全局定义二进制向量 $q$，$q_i=1$ 代表最终枚举的周期向量中必定存在 $v_i=1$。我们首先枚举 $\pi(v)$，显然的要求是对于 $1\le i<\pi(v)$ 有 $q_i\ne1$。有三种情况：
- $\pi(v)\le\left\lfloor\frac{|v|}2\right\rfloor$。我们首先检查 $q$ 中的元素是否和 $\pi(v)$ 冲突（即，是否存在 $i$ 使得 $p\nmid i$ 且 $q_i=1$），然后将所有 $p$ 的所有小于 $|v|$ 的倍数 $i$ 标记 $q_i=1$，接着递归到 $n’=n-r$ 继续进行枚举。
- $\pi(v)>\left\lfloor\frac{|v|}2\right\rfloor$ 且 $\pi(v)\ne+\infty$。我们直接递归到 $n’=n-\pi(v)$ 进行枚举。
- $\pi(v)=+\infty$。这种情况我们已经找到了一种合法的 $v$，将其输出并返回。
我们观察到这样的枚举算法的时间复杂度大致是和本质不同的 $c_w(x)$ 个数成正比的。现在我们考虑如何同时计算出字符串的自由元数目。还是对上面三种情况考虑（下图连线表示两段子串相同）：
- $\pi(v)\le\left\lfloor\frac{|v|}2\right\rfloor$（图一）。此时整个字符串的自由元数目等价于剩下那一段的自由元数目，不需要额外添加。
- $\pi(v)>\left\lfloor\frac{|v|}2\right\rfloor$（图二）。自由元数目等价于圈起来的一部分加上后面剩下一部分的自由元。
- $\pi(v)=+\infty$。自由元数目为 $0$。
这里 给出了一个示例的程序，在我的电脑上能够在五分钟内给出所有 $n\le 60$ 的合法周期向量及其方案数。
目前程序的瓶颈在于 $O(\text{本质不同周期向量数目}^2)$ 的计算 $f_v$。如果要对其进行改进，我们需要维护支持如下操作的数据结构：
-
$insert(x,v)$：插入二元组 $(x,v)$，其中 $x$ 为一个集合（集合元素值域即为 $[1,n]$），$v$ 为整数。
-
$query(y)$：统计所有满足 $x\supseteq y$ 的二元组 $(x,v)$ 中 $v$ 的和。
显然可以二进制分为两个部分维护，但是并没有将复杂度显著降低。如果有更好的做法欢迎联系作者。
