浅谈“随机按键指定串”问题
zls_XICK
·
·
算法·理论
Preface
主要作为培训时该类问题的总结。
Link CSDN Blog
Introduction
这类问题的主要形式是：
有 m 个不同的字符按键，进行 n 次（或无限次）随机敲打。
询问 n 个字符中出现长度为 k 的指定串 S 的概率。
或求无限次敲打中 S 出现位置的期望。
首先，这个问题是与 KMP 有关的，我们知道 \rm{Border} 串是原串的前后缀，那么从感性的角度理解，\rm{Border} 越长，S 越容易在匹配失败时恢复更长的前缀，使得出现概率更大、位置期望更靠前。
对于问题“n 个字符中出现长度为 k 的指定串 S 的概率”，题目：
Mivik 的标题
这个问题实际上很古老，\rm{Border} 理论中有 \rm{Border} 串可分为 O(\log k) 个等差数列的描述，根据推出的 DP 式子使用该理论与半在线卷积、高斯消元、多项式求逆、生成函数等操作便可以有效地求出。
在该题目的题解区已有丰富的解答，这里不多赘言。
而对于问题“无限次敲打中 S 出现位置的期望”，理论上可以运用上面的结论，在无限求和中使用数列等合并的方法。
但实际上对于无限问题，如果是收敛的，期望递推式并不会过于丑陋。
记 f_i 为 S 第 i 位到 S 最后一个字符出现的期望，根据 KMP 自动机有这么一个函数：
\delta(i,c)=\begin{cases}
i+1, & c=s_{i+1} \\
\delta(\pi_i,c), & else
\end{cases}
其中 \pi_i 即位置 i 的 \rm{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_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})}$$
$\rm{Border}$ 串预处理，$\delta$ 函数是 $O(\log k)$ 的，于是这就是一个普通的 $O(n \log k)$ 递推式子。
我们要的位置期望就是 $f_0$，也就是 $f_k-g_k$，$f_k$ 已经代表 $S$ 的最后一个位置了，敲打次数期望为 $0$，则 $f_0=-g_k$。
这样我们避免了复杂的数学推演，只使用了简单的期望递推，本问题就此告段落。
一个古老的类似问题：
[[CTSC2006] 歌唱王国](https://www.luogu.com.cn/problem/P4548)
希望本文章对你有帮助。