Preface

主要作为培训时该类问题的总结。

Introduction

这类问题的主要形式是：

有 $m$ 个不同的字符按键，进行 $n$ 次（或无限次）随机敲打。

询问 $n$ 个字符中出现长度为 $k$ 的指定串 $S$ 的概率。

或求无限次敲打中 $S$ 出现位置的期望。

首先，这个问题是与 KMP 有关的，我们知道 $\mathrm{Border}$ 串是原串的前后缀，那么从感性的角度理解，$\mathrm{Border}$ 越长，$S$ 越容易在匹配失败时恢复更长的前缀，使得出现概率更大、位置期望更靠前。

对于问题“$n$ 个字符中出现长度为 $k$ 的指定串 $S$ 的概率”，题目：

Mivik 的标题

这个问题实际上很古老，$\mathrm{Border}$ 理论中有 $\mathrm{Border}$ 串可分为 $O(\log k)$ 个等差数列的描述，根据推出的 DP 式子使用该理论与半在线卷积、高斯消元、多项式求逆、生成函数等操作便可以有效地求出。

在该题目的题解区已有丰富的解答，这里不多赘言。

而对于问题“无限次敲打中 $S$ 出现位置的期望”，理论上可以运用上面的结论，在无限求和中使用数列等合并的方法。

但实际上对于无限问题，如果是收敛的，期望递推式并不会过于丑陋。

记 $f_i$ 为 $S$ 第 $i$ 位到 $S$ 最后一个字符出现的期望，根据 KMP 自动机有这么一个函数：

$$\delta (i,c)=\{\begin{array}{ll}i+1,& c=s_{i+1}\\ \delta ({\pi }_i,c),& else\end{array}$$

其中 ${\pi }_i$ 即位置 $i$ 的 $\mathrm{Border}$ 长度。

所以把 $f_i$ 拆分可能的转移易得：

$$f_i=\frac{1}{m}\sum _c{f}_{\delta (i,c)}+1$$

我们对比 $f_{{\pi }_i}$：

$$f_{{\pi }_i}=\frac{1}{m}\sum _c{f}_{\delta ({\pi }_i,c)}+1$$

做一次容斥：

$$f_i=f_{{\pi }_i}-\frac{1}{m}{f}_{\delta ({\pi }_i,s_{i+1})}+\frac{1}{m}{f}_{i+1}$$

$f_i$ 作为期望的定义是倒着走的，我们为了方便处理，设 $g_i=f_i-f_0$，那么显然 $g_0=0$。

而由前面：

$$f_0=\frac{1}{m}\sum _c{f}_{\delta (0,c)}+1=\frac{1}{m}{f}_1+\frac{m-1}{m}{f}_0+1$$

化简有 $f_1-f_0=-m$，也就是 $g_1=-m$。

把 $g_i$ 代入容斥后的式子：

$$g_i+f_0=g_{{\pi }_i}+f_0-\frac{1}{m}(g_{\delta ({\pi }_i,s_{i+1})}+f_0)+\frac{1}{m}(g_{i+1}+f_0)$$

不难发现 $f_0$ 可以消掉：

$$g_{i+1}=m(g_i-g_{{\pi }_i})+g_{\delta ({\pi }_i,s_{i+1})}$$

$\mathrm{Border}$ 串预处理，$\delta$ 函数是 $O(\log k)$ 的，于是这就是一个普通的 $O(n\log k)$ 递推式子。

我们要的位置期望就是 $f_0$，也就是 $f_k-g_k$，$f_k$ 已经代表 $S$ 的最后一个位置了，敲打次数期望为 $0$，则 $f_0=-g_k$。

这样我们避免了复杂的数学推演，只使用了简单的期望递推，本问题就此告段落。

一个古老的类似问题：

[CTSC2006] 歌唱王国

希望本文章对你有帮助。