正文
【XSY2472】string KMP 期望DP
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
题目大意
给定一个由且仅由字符'H'，'T'构成的字符串\(S\)。
给定一个最初为空的字符串\(T\) ，每次随机地在\(T\)的末尾添加'H'或者'T'。
问当\(S\)为\(T\)的后缀时，在末尾添加字符的期望次数。
对\({10}^9+7\)取模
题解
设\(f_i\)为从\(i-1\)匹配到\(i\)期望的匹配次数，\(g_i\)表示匹配到\(i\)后下一次失配能匹配到什么位置（用KMP求），\(s_i=\sum_{j=1}^if_j\)
考虑匹配到第\(i\)位的情况：
\[f_i=\frac12\times 1+\frac12(1+f_{g_{i-1}+1}+f_{g_{i-1}+2}+\cdots f_{i})\\
f_i=2+s_{i-1}-s_{g_{i-1}}
\]
f_i=2+s_{i-1}-s_{g_{i-1}}
\]
答案为\(s_n\)
时间复杂度：\(O(n)\)
代码
