題目大意

　　給定一個由且僅由字符'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}} \]
　　答案為\(s_n\)

　　時間復雜度：\(O(n)\)

代碼

轉載于:https://www.cnblogs.com/ywwyww/p/8511045.html

總結

以上是生活随笔為你收集整理的【XSY2472】string KMP 期望DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。