浅谈“随机按键指定串”问题

Preface主要作为培训时该类问题的总结。Introduction这类问题的主要形式是有m mm个不同的字符按键进行n nn次或无限次随机敲打。询问n nn个字符中出现长度为k kk的指定串S SS的概率。或求无限次敲打中S SS出现位置的期望。首先这个问题是与 KMP 有关的我们知道B o r d e r \rm{Border}Border串是原串的前后缀那么从感性的角度理解B o r d e r \rm{Border}Border越长S SS越容易在匹配失败时恢复更长的前缀使得出现概率更大、位置期望更靠前。对于问题“n nn个字符中出现长度为k kk的指定串S SS的概率”题目Mivik 的标题这个问题实际上很古老B o r d e r \rm{Border}Border理论中有B o r d e r \rm{Border}Border串可分为O ( log ⁡ k ) O(\log k)O(logk)个等差数列的描述根据推出的 DP 式子使用该理论与半在线卷积、高斯消元、多项式求逆、生成函数等操作便可以有效地求出。在该题目的题解区已有丰富的解答这里不多赘言。而对于问题“无限次敲打中S SS出现位置的期望”理论上可以运用上面的结论在无限求和中使用泰勒等多项式合并的方法。但实际上对于无限问题如果是收敛的期望递推式并不会过于丑陋。记f i f_ifi​为S SS第i ii位到S SS最后一个字符出现的期望根据 KMP 自动机有这么一个函数δ ( i , c ) { i 1 , c s i 1 δ ( π i , c ) , e l s e \delta(i,c)\begin{cases} i1, cs_{i1} \\ \delta(\pi_i,c), else \end{cases}δ(i,c){i1,δ(πi​,c),​csi1​else​其中π i \pi_iπi​即位置i ii的B o r d e r \rm{Border}Border长度。所以把f i f_ifi​拆分可能的转移易得f i 1 m ∑ c f δ ( i , c ) 1 f_i\frac{1}{m}\sum_{c} f_{\delta(i,c)}1fi​m1​c∑​fδ(i,c)​1我们对比f π i f_{\pi_i}fπi​​f π i 1 m ∑ c f δ ( π i , c ) 1 f_{\pi_i}\frac{1}{m}\sum_{c} f_{\delta(\pi_i,c)}1fπi​​m1​c∑​fδ(πi​,c)​1做一次容斥f i f π i − 1 m f δ ( π i , s i 1 ) 1 m f i 1 f_if_{\pi_i}-\frac{1}{m}f_{\delta(\pi_i,s_{i1})}\frac{1}{m}f_{i1}fi​fπi​​−m1​fδ(πi​,si1​)​m1​fi1​f i f_ifi​作为期望的定义是倒着走的我们为了方便处理设g i f i − f 0 g_if_i-f_0gi​fi​−f0​那么显然g 0 0 g_00g0​0。而由前面f 0 1 m ∑ c f δ ( 0 , c ) 1 1 m f 1 m − 1 m f 0 1 f_0\frac{1}{m}\sum_{c} f_{\delta(0,c)}1\frac{1}{m}f_1\frac{m-1}{m}f_01f0​m1​c∑​fδ(0,c)​1m1​f1​mm−1​f0​1化简记f 1 − f 0 − m f_1-f_0-mf1​−f0​−m也就是g 1 − m g_1-mg1​−m。把g i g_igi​代入容斥后的式子g i f 0 g π i f 0 − 1 m ( g δ ( π i , s i 1 ) f 0 ) 1 m ( g i 1 f 0 ) g_if_0g_{\pi_i}f_0-\frac{1}{m}(g_{\delta(\pi_i,s_{i1})}f_0)\frac{1}{m}(g_{i1}f_0)gi​f0​gπi​​f0​−m1​(gδ(πi​,si1​)​f0​)m1​(gi1​f0​)不难发现f 0 f_0f0​可以消掉g i 1 m ( g i − g π i ) g δ ( π i , s i 1 ) g_{i1}m(g_i-g_{\pi_i})g_{\delta(\pi_i,s_{i1})}gi1​m(gi​−gπi​​)gδ(πi​,si1​)​B o r d e r \rm{Border}Border串预处理δ \deltaδ函数是O ( log ⁡ k ) O(\log k)O(logk)的于是这就是一个普通的O ( n log ⁡ k ) O(n \log k)O(nlogk)递推式子。我们要的位置期望就是f 0 f_0f0​也就是f k − g k f_k-g_kfk​−gk​f k f_kfk​已经代表S SS的最后一个位置了敲打次数期望为0 00则f 0 − g k f_0-g_kf0​−gk​。这样我们避免了复杂的数学推演只使用了简单的期望递推本问题就此告段落。一个古老的类似问题[CTSC2006] 歌唱王国希望本文章对你有帮助。