COCI20162017 Contest#7 F

沿用上面的定义，设字符串$S$的$\text{border}$集合为$B(S)$

考虑对于单串$S$求答案，设答案为$Ans$

将所有可能出现的字符串分为两个集合$A,B$

其中$A$为所有恰好出现$S$的字符串集合，$B$为所有还未出现匹配的字符串集合

我们知道每个字符串出现有一定的概率，即为$\frac{1} {n^{|T|} }$

设$A$集合中所有长度为$i$的串出现的概率总和为$A_i$，同理得到$B_i$

$A$中的概率是不重复的，因为每个匹配过程只有一次会恰好匹配，因此可以得到 $\sum A_i=1$

(而$B$中每个不匹配的串概率会被算多次)

最后的答案期望可以表示为

1.每个匹配的串概率*匹配时串的长度之和，即$Ans=\sum_i i\cdot A_i$

2.将匹配成功的长度，转化为匹配失败的次数之和(包含空串)，可以表示为$Ans=\sum B_i$

直接计算似乎比较麻烦

$\$

考虑如果在$B$中所有字符串的后面接上一个原串$S$（同时概率乘上$\frac{1} {n^{|S|} }$），那么得到的新字符串一定完成匹配

但是实际上，这样的串并不一定完全合法，因为可能在更早的位置出现匹配

由上面的定义，假设原先在$B$中的串为$T$，原先已经在$S$中匹配了$T’$作为前缀

那么直接强行加上$S$后，如果$T’$会影响第一个出现匹配位置，设出现匹配时加入的字符串为$R$

则显然满足: $R$即是$S$的一段前缀，又是$S$的一段后缀，也就是$R\in B(S)$

而剩下部分($|S|-|R|$)，实际上是无效的，因此概率会被算小了

$\$

不妨设$B$集合接上一个$S$串得到的集合为$C$

可以把$C$中的字符串，按照多余的部分$|S|-|R|$为多个部分$D_{R}$其中$R\in B(S)$

发现，实际上去掉多余的部分后，每个$D_R$集合就与$A$集合对应，但是多余部分的要乘回去

即 $A_i=D_{|R|,i+|S|-|R|}\cdot n^{|S|-|R|}$ (偏移多出的部分)

由$B,C$的关系，有$\sum_R D_{R,i}=C_i=B_i\cdot \frac{1} {n^{|S|} }$

也就是$B_i\frac{1} {n^{|S|} }=\sum _R D_{R,i+|S|-|R|}=\sum _R \frac{A_{i+|S|-|R|} } {n^{|S|-|R|} }$

即 $B_i=\sum _R A_{i+|S|-|R|}n^{|R|}$

将上式求和对于$i$求和，得到$\sum B_i=\sum_i\sum_R A_{i+|S|-|R|}n^{|R|}$

由于$\sum A_i=1$ ($\sum A_i$和$\sum A_{i+|S|-|R|}$等价)，即

$Ans=\sum B_i=\sum_{R\in B(S)} n^{|R|}$

orangejuice's blog